Inverse monoids of dot-depth two

DOI10.1016/0304-3975(89)90151-5zbMath0678.68075MaRDI 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 monoids; dot-depth hierarchy; star-free regular languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q70: Algebraic theory of languages and automata

Related Items

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, Equations and monoid varieties of dot-depth one and two, Polynomial closure and unambiguous product, Logic, semigroups and automata on words, Some complexity results for polynomial rational expressions., Inclusion relations between some congruences related to the dot-depth hierarchy, 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