On a conjecture concerning dot-depth two languages

DOI10.1016/0304-3975(92)90121-UzbMath0762.68037OpenAlexW2066702102WikidataQ123140748 ScholiaQ123140748MaRDI QIDQ1200802

Howard Straubing, Pascal Weil

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90121-u

zbMATH Keywords

semigroupdot-depth hierarchystar-free regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

Polynomial closure and unambiguous product ⋮ Polynomial closure and unambiguous product ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ The product of rational languages ⋮ Locally commutative power semigroups and counting factors of words ⋮ Some results on the dot-depth hierarchy ⋮ The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin ⋮ A counterexample to a conjecture concerning concatenation hierarchies ⋮ Logic, semigroups and automata on words ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ Algebraic tools for the concatenation product. ⋮ A conjecture on the concatenation product

Cites Work

• 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
• Presentations of inverse monoids
• On generalized locally testable languages
• The kernel of monoid morphisms
• The lattices of varieties and pseudovarieties of band monoids
• Semigroups and languages of dot-depth two
• Inverse monoids of dot-depth two
• Une topologie du monoide libre
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Finite semigroup varieties of the form V*D
• The lattice of equational classes of idempotent semigroups
• Dot-depth of star-free events
• Characterizations of locally testable events
• Finite monoids and the fine structure of NC ¹
• On finite monoids having only trivial subgroups

This page was built for publication: On a conjecture concerning dot-depth two languages