Journalartikel

Jahr der Veröffentlichung: 2023

Zeitschrift: RAIRO: Theoretical Informatics and Applications

Bandnummer: 57

ISSN: 0988-3754

eISSN: 2804-7346

Open Access Status: Hybrid

DOI Link: https://doi.org/10.1051/ita/2023010

Verlag: EDP Sciences

Abstract: 
We investigate the accepting state complexity of deterministic finite automata for regular languages obtained by applying one of the following operations on languages accepted by permutation automata: union, quotient, complement, difference, intersection, Kleene star, Kleene plus, and reversal. The paper thus joins the study of the accepting state complexity of regularity preserving language operations which was initiated in [J. Dassow, J. Autom., Lang. Comb. 21 (2016) 55-67]. We show that for almost all of the above-mentioned 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 numbers 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.

Harvard-Zitierstil: Rauch, C. and Holzer, M. (2023) On the accepting state complexity of operations on permutation automata, RAIRO: Theoretical Informatics and Applications, 57, Article 9. https://doi.org/10.1051/ita/2023010

APA-Zitierstil: Rauch, C., & Holzer, M. (2023). On the accepting state complexity of operations on permutation automata. RAIRO: Theoretical Informatics and Applications. 57, Article 9. https://doi.org/10.1051/ita/2023010