On the Accepting State Complexity of Operations on Permutation Automata Article Swipe
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4204/eptcs.367.12
· OA: W4293325636
We investigate the accepting state complexity of deterministic finite\nautomata for regular languages obtained by applying one of the following\noperations to languages accepted by permutation automata: union, quotient,\ncomplement, difference, intersection, Kleene star, Kleene plus, and reversal.\nThe paper thus joins the study of accepting state complexity of regularity\npreserving language operations which was initiated by the work [J. Dassow: On\nthe number of accepting states of finite automata, J. Autom., Lang. Comb., 21,\n2016]. We show that for almost all of the operations, except for reversal and\nquotient, there is no difference in the accepting state complexity for\npermutation automata compared to deterministic finite automata in general. For\nboth reversal and quotient we prove that certain accepting state complexities\ncannot be obtained; these number are called "magic" in the literature.\nMoreover, we solve the left open accepting state complexity problem for the\nintersection of unary languages accepted by permutation automata and\ndeterministic finite automata in general.\n
