Regular languages and partial commutations

DOI10.1016/j.ic.2013.07.003zbMath1358.68202OpenAlexW2162512015MaRDI QIDQ391641

Giovanna Guaiana, Antonio Cano, Jean-Eric Pin

Publication date: 10 January 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2013.07.003

zbMATH Keywords

shuffleregular languagepartial commutationtrace languagevariety of languages

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Related Items

Constrained synchronization for monotonic and solvable automata and automata with simple idempotents ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Unnamed Item ⋮ The Shuffle Product: New Research Directions ⋮ Geometrically closed positive varieties of languages ⋮ Commutative regular languages with product-form minimal automata ⋮ Rational subsets and submonoids of wreath products. ⋮ The commutative closure of shuffle languages over group languages is regular ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints

Uses Software

• Semigroupe

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the commutative closure of star-free languages
• On hereditary properties of the class of graphs with convex quadratic stability number
• Permutation rewriting and algorithmic verification
• An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable
• On total regulators generated by derivation relations
• Semi-commutations
• Paw-free graphs
• Complement reducible graphs
• Polynomial closure of group languages and open sets of the Hall topology
• Polynomial closure and unambiguous product
• Shuffle on positive varieties of languages
• Semigroups, Presburger formulas, and languages
• Efficiency of automata in semi-commutation verification techniques
• When Does Partial Commutative Closure Preserve Regularity?
• SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
• A Star Operation for Star-Free Trace Languages
• Bounded Regular Sets