Shuffle on positive varieties of languages

DOI10.1016/j.tcs.2003.10.034zbMath1143.68431OpenAlexW2063190464MaRDI QIDQ1884959

Jean-Eric Pin, Antonio Cano Gómez

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.034

zbMATH Keywords

LanguagesFinite AutomataOrdered semigroupsVarieties shuffle

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages ⋮ A positive extension of Eilenberg's variety theorem for non-regular languages ⋮ Shuffled languages -- representation and recognition ⋮ Regular languages and partial commutations ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Shuffle product of regular languages: results and open problems ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Efficiency of automata in semi-commutation verification techniques ⋮ Upper set monoids and length preserving morphisms ⋮ The expressive power of the shuffle product ⋮ A Robust Class of Regular Languages ⋮ The Shuffle Product: New Research Directions ⋮ On fixed points of the lower set operator ⋮ Geometrically closed positive varieties of languages ⋮ Positive varieties of tree languages ⋮ Regularity conditions for iterated shuffle on commutative regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local languages and the Berry-Sethi algorithm
• Recognizable sets and power sets of finite semigroups
• Variétés de langages et monoide des parties
• The Birkhoff theorem for finite algebras
• Some results on the generalized star-height problem
• Sur le monoide syntactique de \(L^*\)lorsque L est un langage fini
• Variétés de langages et opérations
• Modeling literal morphisms by shuffle
• Algebraic tools for the concatenation product.
• A Reiterman theorem for pseudovarieties of finite first-order structures
• Process Algebra
• SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
• ORDERED CATEGORIES AND ORDERED SEMIGROUPS
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS