论文标题
对群体语言的换档表达方式的交换是常规的
The Commutative Closure of Shuffle Expressions over Group Languages is Regular
论文作者
论文摘要
我们表明，交换性的闭合与迭代的混音相结合是对集体语言的规律性保护操作。特别是，对于交换式语言，迭代的洗牌是一种规律性的保护操作。我们还为最小识别自动机的大小提供了界限。然后，我们使用这些结果来推断出对群体语言的任何混乱表达的交换闭合，即涉及涉及洗牌，迭代洗牌，串联，Kleene Star和Union的表达方式，以任何顺序从群体语言开始，总是会产生常规语言。
We show that the commutative closure combined with the iterated shuffle is a regularity-preserving operation on group languages. In particular, for commutative group languages, the iterated shuffle is a regularity-preserving operation. We also give bounds for the size of minimal recognizing automata. Then, we use these results to deduce that the commutative closure of any shuffle expression over group languages, i.e., expressions involving shuffle, iterated shuffle, concatenation, Kleene star and union in any order, starting with the group languages, always yields a regular language.
