On the accepting state complexity of operations on permutation automata

DOI10.1051/ITA/2023010MaRDI QIDQ6186540zbMATH OpenOpenAlexFDO

Authors Christian Rauch, Markus Holzer

Publication date 2 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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)

Abstract: We investigate the accepting state complexity of deterministic finite automata for regular languages obtained by applying one of the following operations to languages accepted by permutation automata: union, quotient, complement, difference, intersection, Kleene star, Kleene plus, and reversal. The paper thus joins the study of accepting state complexity of regularity preserving language operations which was initiated by the work [J. Dassow: On the number of accepting states of finite automata, J. Autom., Lang. Comb., 21, 2016]. We show that for almost all of the operations, except for reversal and quotient, there is no difference in the accepting state complexity for permutation automata compared to deterministic finite automata in general. For both reversal and quotient we prove that certain accepting state complexities cannot be obtained; these number are called "magic" in the literature. Moreover, we solve the left open accepting state complexity problem for the intersection of unary languages accepted by permutation automata and deterministic finite automata in general.

Recommendations

• On the accepting state complexity of operations on permutation automata
• Operations on Permutation Automata
• The ranges of accepting state complexities of languages resulting from some operations
• The ranges of accepting state complexities of languages resulting from some operations
• The state complexity of permutations on finite languages over binary alphabets

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 7730620 (Why is no real title available?)
• A survey on operational state complexity
• On the number of accepting states of finite automata
• Operations on Permutation Automata
• Set-Transitive Permutation Groups
• The range of state complexities of languages resulting from the cascade product -- the unary case (extended abstract)
• The ranges of accepting state complexities of languages resulting from some operations
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• Yet another proof of the cascade decomposition theorem for finite automata

Cited in

(3)

• On the accepting state complexity of operations on permutation automata
• Operations on Permutation Automata
• Decision problems for reversible and permutation automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186540)