Utilize este identificador para referenciar este registo: https://hdl.handle.net/10216/176485
Registo completo
Campo DCValorIdioma
dc.creatorBroda, S
dc.creatorAntónio Machiavelo
dc.creatorNelma Moreira
dc.creatorRogério Reis
dc.date.accessioned2026-09-01T01:36:48Z-
dc.date.available2026-09-01T01:36:48Z-
dc.date.issued2025
dc.identifier.othersigarra:758976
dc.identifier.urihttps://hdl.handle.net/10216/176485-
dc.description.abstractConsidering 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.isoeng
dc.relation.ispartofDESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2025
dc.rightsopenAccess
dc.titleAutomata for Synchronised Shuffle on Backbones
dc.typeArtigo em Livro de Atas de Conferência Internacional
dc.contributor.uportoFaculdade de Ciências
dc.identifier.doi10.1007/978-3-031-97100-6_5
dc.identifier.authenticusP-019-J8E
Aparece nas coleções:FCUP - Artigo em Livro de Atas de Conferência Internacional

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
758976.pdfFinal version430.12 kBAdobe PDFThumbnail
Ver/Abrir


Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.