Equations and monoid varieties of dot-depth one and two

DOI10.1016/0304-3975(92)00064-XzbMath0801.68105OpenAlexW2008933300MaRDI QIDQ1314381

Francine Blanchet-Sadri

Publication date: 22 February 1994

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

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

zbMATH Keywords

aperiodic monoidsstar-free languagesStraubing hierarchydot-depth

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (20)

On the Complexity of k-Piecewise Testability and the Depth of Automata ⋮ Representations and identities of plactic-like monoids ⋮ Identities of the stylic monoid ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ Equations on the semidirect product of a finite semilattice by a $\mathcal {J}$-trivial monoid of height $k$ ⋮ The finite basis problem for Kiselman monoids. ⋮ Tropical representations and identities of the stylic monoid ⋮ Catalan monoids inherently nonfinitely based relative to finite \(\mathscr{R}\)-trivial semigroups ⋮ On the word problem for syntactic monoids of piecewise testable languages. ⋮ Hierarchies of Piecewise Testable Languages ⋮ Identities in unitriangular and gossip monoids ⋮ Normal forms under Simon's congruence ⋮ Finite basis problem for involution monoids of unitriangular Boolean matrices ⋮ REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT ⋮ HIERARCHIES OF PIECEWISE TESTABLE LANGUAGES ⋮ Equational theories of upper triangular tropical matrix semigroups ⋮ Non-finitely based monoids. ⋮ Finitely based monoids. ⋮ SUBHIERARCHIES OF THE SECOND LEVEL IN THE STRAUBING–THÉRIEN HIERARCHY ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equations and dot-depth one
• First-order logic and star-free sets
• Inverse monoids of dot-depth two
• Classifying regular events in symbolic logic
• Games, equations and dot-depth two monoids
• On pseudovarieties
• The dot-depth hierarchy of star-free languages is infinite
• Games, equations and the dot-depth hierarchy
• Some logical characterizations of the dot-depth hierarchy and applications
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• On finite monoids having only trivial subgroups
• On dot-depth two

This page was built for publication: Equations and monoid varieties of dot-depth one and two