On a conjecture concerning dot-depth two languages

DOI10.1016/0304-3975(92)90121-UMaRDI QIDQ1200802zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• Inverse monoids of dot-depth two
• On dot-depth two
• INVERSE MONOIDS OF DOT-DEPTH TWO
• Semigroups and languages of dot-depth two
• Some logical characterizations of the dot-depth hierarchy and applications

Cites work

• scientific article; zbMATH DE number 3827223 (Why is no real title available?)
• scientific article; zbMATH DE number 3961008 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 3552814 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3640907 (Why is no real title available?)
• scientific article; zbMATH DE number 3071073 (Why is no real title available?)
• Categories as algebra: An essential ingredient in the theory of monoids
• Characterizations of locally testable events
• Classifying regular events in symbolic logic
• Dot-depth of star-free events
• Finite monoids and the fine structure of NC ¹
• Finite semigroup varieties of the form V*D
• Inverse monoids of dot-depth two
• On finite monoids having only trivial subgroups
• On generalized locally testable languages
• Presentations of inverse monoids
• Semigroups and languages of dot-depth two
• The dot-depth hierarchy of star-free languages is infinite
• The kernel of monoid morphisms
• The lattice of equational classes of idempotent semigroups
• The lattices of varieties and pseudovarieties of band monoids
• Une topologie du monoide libre

Cited in

(18)

• Locally commutative power semigroups and counting factors of words
• Dot-depth three, return of the j-class
• scientific article; zbMATH DE number 1500543 (Why is no real title available?)
• Some results on the dot-depth hierarchy
• Inverse monoids of dot-depth two
• A counterexample to a conjecture concerning concatenation hierarchies
• The product of rational languages
• Algebraic tools for the concatenation product.
• Semigroups and languages of dot-depth two
• The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin
• Polynomial closure and unambiguous product
• Polynomial closure and unambiguous product
• Logic, semigroups and automata on words
• A conjecture on the concatenation product
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Languages of dot-depth 3/2
• On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids
• scientific article; zbMATH DE number 3961008 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1200802)