On the accepting state complexity of operations on permutation automata

DOI10.1051/ita/2023010arXiv2208.14731OpenAlexW4388468733MaRDI QIDQ6186540

Markus Holzer, Christian Rauch

Publication date: 2 February 2024

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.14731

zbMATH Keywords

descriptional complexitypermutation automatalanguage operationsaccepting state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• The ranges of accepting state complexities of languages resulting from some operations
• The range of state complexities of languages resulting from the cascade product -- the unary case (extended abstract)
• On the Number of Accepting States of Finite Automata
• Operations on Permutation Automata
• Yet another proof of the cascade decomposition theorem for finite automata
• Set-Transitive Permutation Groups

This page was built for publication: On the accepting state complexity of operations on permutation automata