Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10216/176485Registo completo
| Campo DC | Valor | Idioma |
|---|---|---|
| dc.creator | Broda, S | |
| dc.creator | António Machiavelo | |
| dc.creator | Nelma Moreira | |
| dc.creator | Rogério Reis | |
| dc.date.accessioned | 2026-09-01T01:36:48Z | - |
| dc.date.available | 2026-09-01T01:36:48Z | - |
| dc.date.issued | 2025 | |
| dc.identifier.other | sigarra:758976 | |
| dc.identifier.uri | https://hdl.handle.net/10216/176485 | - |
| dc.description.abstract | Considering regular expressions extended with synchronised shuffle on backbones, we present two equivalent automata: the location based position automaton and the partial derivative automaton. We show that the latter is a quotient of the former. Using the framework of analytic combinatorics, we study the average complexity of the partial derivative automaton. Surprisingly, for binary and ternary alphabets the average number of partial derivatives by a symbol is exponential on the size of the expression, while it is constant for larger alphabets which is what happens with the results for all other regular operators studied so far. Furthermore, we prove that the average number of states of the partial derivative automaton is bounded from above by (1.57708 + o(1))(m), while in the worst-case that value is O(3(m)), where m is the alphabetic size of the expression. | |
| dc.language.iso | eng | |
| dc.relation.ispartof | DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2025 | |
| dc.rights | openAccess | |
| dc.title | Automata for Synchronised Shuffle on Backbones | |
| 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-031-97100-6_5 | |
| dc.identifier.authenticus | P-019-J8E | |
| Aparece nas coleções: | FCUP - Artigo em Livro de Atas de Conferência Internacional | |
Ficheiros deste registo:
| Ficheiro | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 758976.pdf | Final version | 430.12 kB | Adobe PDF | ![]() Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.
