论文标题
关于置换自动机的接受状态复杂性
On the Accepting State Complexity of Operations on Permutation Automata
论文作者
论文摘要
我们研究了通过将以下操作之一应用于置换自动机接受的语言中获得的普通语言的确定性有限自动机的接受状态复杂性：联合，商，补充，差异，差异，交点，kleene star，kleene plus和kleene plus和逆转。因此，本文加入了接受规律性保留语言操作的国家复杂性的研究，这是由工作发起的[J. Dassow：关于有限自动机的接受状态，J。Autom。，Lang。梳子，2016年2月]。 我们表明，对于几乎所有操作，除了逆转和商，与一般确定性有限自动机相比，置换自动机的接受状态复杂性没有差异。对于逆转和商，我们证明无法获得某些接受状态复杂性；这些数字在文献中被称为“魔术”。此外，我们解决了列出的自动机和确定性有限自动机接受的一般语言的交集，解决了左开的接受状态复杂性问题。
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.
