2020/08/12 by Stefan Hoffmann, Hoffmann, Stefan
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q45 (Primary) 68Q19 (Secondary) #Advanced Algebra and Logic #Chemical Synthesis and Analysis #F.1.3 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2008.05420
openalex publication_date 2020/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the commutative closure combined with the iterated shuffle is a\nregularity-preserving operation on group languages. In particular, for\ncommutative group languages, the iterated shuffle is a regularity-preserving\noperation. We also give bounds for the size of minimal recognizing automata.\nThen, we use these results to deduce that the commutative closure of any\nshuffle expression over group languages, i.e., expressions involving shuffle,\niterated shuffle, concatenation, Kleene star and union in any order, starting\nwith the group languages, always yields a regular language.\n