State Complexity Investigations on Commutative Languages -- The Upward\n and Downward Closure, Commutative Aperiodic and Commutative Group Languages

2021/11/26 by Stefan Hoffmann, Hoffmann, Stefan
Computer Science · #Advanced Algebra and Logic #Coding theory and cryptography #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2111.13524

openalex publication_date 2021/11/26 · openalex created_date 2022/11/06 · openalex updated_date 2026/07/28

Abstract

We investigate the state complexity of the upward and downward closure and\ninterior operations on commutative regular languages. Then, we systematically\nstudy the state complexity of these operations and of the shuffle operation on\ncommutative group languages and commutative aperiodic (or star-free) languages.\n

Related

• A combinatorial approach for the state complexity of the Shuffle product
• State Complexity Bounds for the Commutative Closure of Group Languages
• Commutative Regular Languages with Product-Form Minimal Automata
• The Commutative Closure of Shuffle Expressions over Group Languages is\n Regular
• Towards a Theory of Complexity of Regular Languages