论文标题
国家复杂性的界限，以结束群体语言
State Complexity Bounds for the Commutative Closure of Group Languages
论文作者
论文摘要
在这项工作中，我们构建了一个自动机，用于交换给定的常规组语言。产生的自动机的状态数受原始自动机的状态数量的界限，该状态升至字母大小的功率，时间是字母顺序的乘积，被视为状态集的排列。这给出了渐近状态绑定$ o（（（n \ exp（\ sqrt {n \ ln n}）））^{|σ|}）$，如果原始常规语言被带有$ n $ state的自动机接受。根据所讨论的自动机，我们通过状态子集标记$ \ mathbb n_0^{|σ|} $的点，并介绍分解这样标记的网格的Unary Automata。基于这些结构，我们提供了一般的规律性条件，该条件可用于群体语言。
In this work we construct an automaton for the commutative closure of a given regular group language. The number of states of the resulting automaton is bounded by the number of states of the original automaton, raised to the power of the alphabet size, times the product of the order of the letters, viewed as permutations of the state set. This gives the asymptotic state bound $O((n\exp(\sqrt{n\ln n}))^{|Σ|})$, if the original regular language is accepted by an automaton with $n$ states. Depending on the automaton in question, we label points of $\mathbb N_0^{|Σ|}$ by subsets of states and introduce unary automata which decompose the thus labelled grid. Based on these constructions, we give a general regularity condition, which is fulfilled for group languages.
