State complexity bounds for the commutative closure of group languages

DOI10.1007/978-3-030-62536-8_6MaRDI QIDQ2040410zbMATH OpenOpenAlexFDO

Authors Stefan Hoffmann

Publication date 14 July 2021

Full work available at URL https://arxiv.org/abs/2004.11772

zbMATH Keywords

commutative closuregroup languagepermutation automatonstate complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• State complexity bounds for the commutative closure of group languages
• State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages
• Commutative regular languages -- properties and state complexity
• Commutative regular languages with product-form minimal automata

Cited in

(9)

• State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages
• Operations on subregular languages and nondeterministic state complexity
• The commutative closure of shuffle languages over group languages is regular
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• State complexity bounds for the commutative closure of group languages
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• Nondeterministic operational complexity in subregular languages
• Simulation by Rounds of Letter-to-Letter Transducers

This page was built for publication: State complexity bounds for the commutative closure of group languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040410)