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

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