On the accepting state complexity of operations on permutation automata

DOI10.1051/ITA/2023010arXiv2208.14731OpenAlexW4388468733MaRDI QIDQ6186540FDOQ6186540

Authors: Christian Rauch, Markus Holzer 

Publication date: 2 February 2024

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

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.

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

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

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

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

Cited In (3)

• On the accepting state complexity of operations on permutation automata
• Decision problems for reversible and permutation automata
• Operations on 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)