On the accepting state complexity of operations on permutation automata

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

Markus Holzer, Christian Rauch

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

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)
• Title not available (Why is that?)
• 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 (1)

• 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)