Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10216/176470Registo completo
| Campo DC | Valor | Idioma |
|---|---|---|
| dc.creator | Duarte, G | |
| dc.creator | Nelma Moreira | |
| dc.creator | Prigioniero, L | |
| dc.creator | Rogério Reis | |
| dc.date.accessioned | 2026-09-01T01:33:04Z | - |
| dc.date.available | 2026-09-01T01:33:04Z | - |
| dc.date.issued | 2026 | |
| dc.identifier.other | sigarra:788018 | |
| dc.identifier.uri | https://hdl.handle.net/10216/176470 | - |
| dc.description.abstract | In this paper, we study the descriptional complexity of several variants of the shuffle operation on regular languages. In the perfect shuffle, words of equal length strictly alternate their symbols. If the words have different lengths, the initial literal shuffle performs the perfect shuffle while both words have symbols and then appends the remaining suffix of the longest word. Lastly, the literal shuffle is an extension of the previous operation, in which the initial shuffle may start at an arbitrary position in one of the two words. We analyze the number of states sufficient and necessary for nondeterministic and deterministic automata to recognize the resulting languages. For nondeterministic finite automata, the cost of the simulation is polynomial. In the worst case, a deterministic finite automaton requires exponentially many states to recognize the literal shuffle of two languages given also by deterministic finite automata, whereas a deterministic.1-limited automatonnamely, a one-tape Turing machine in which each cell may be rewritten only upon its first visit requires only polynomial many states. (c) The Author(s). | |
| dc.language.iso | eng | |
| dc.relation.ispartof | DLT | |
| dc.rights | openAccess | |
| dc.title | On the Descriptional Complexity of Literal Shuffle | |
| dc.type | Artigo em Livro de Atas de Conferência Internacional | |
| dc.contributor.uporto | Faculdade de Ciências | |
| dc.identifier.doi | 10.1007/978-3-032-28404-4_23 | |
| dc.identifier.authenticus | P-01C-NM7 | |
| Aparece nas coleções: | FCUP - Artigo em Livro de Atas de Conferência Internacional | |
Ficheiros deste registo:
| Ficheiro | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 788018.pdf | Final version | 376.67 kB | Adobe PDF | ![]() Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.
