Inverse monoids of dot-depth two

DOI10.1016/0304-3975(89)90151-5zbMath0678.68075OpenAlexW2079443329MaRDI QIDQ1124363

Pascal Weil

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90151-5

zbMATH Keywords

inverse monoidsdot-depth hierarchystar-free regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (12)

Some complexity results for polynomial rational expressions. ⋮ Polynomial closure and unambiguous product ⋮ Polynomial closure and unambiguous product ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ The product of rational languages ⋮ Polynomial operations and hierarchies of concatenation ⋮ AUTOMATE, a computing package for automata and finite semigroups ⋮ On a conjecture concerning dot-depth two languages ⋮ Some results on the dot-depth hierarchy ⋮ Logic, semigroups and automata on words ⋮ Equations and monoid varieties of dot-depth one and two ⋮ A conjecture on the concatenation product

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Categories as algebra: An essential ingredient in the theory of monoids
• First-order logic and star-free sets
• A generalization of the Schützenberger product of finite monoids
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Characterizations of locally testable events
• Weak Second‐Order Arithmetic and Finite Automata
• Parity, circuits, and the polynomial-time hierarchy
• Varieties of finite categories
• Catégories et langages de dot-depth un
• On finite monoids having only trivial subgroups

This page was built for publication: Inverse monoids of dot-depth two