State Complexity Bounds for Shuffle and Iterated Shuffle Combined with the Commutative Closure on Group Languages.
Stefan Hoffmann · arXiv (Cornell University) · 2020
We show that the shuffle and iterated shuffle of the commutative closure of a group language is regular, and derive state bounds for resulting automata. In particular, for commutative group languages the iterated shuffle is a regularity preserving operation. For the shuffle of two commutative group languages, we give a sharp bound. For applying the shuffle operation to the commutative closure of multiple group languages we give a state bound that is better than applying general bounds on individual operations. To derive our results, we introduce the state label method as a unifying framework, which is based on a generalized commutative image and a decomposition thereof into unary automata.