On a complete set of generators for dot-depth two

DOI10.1016/0166-218X(94)90161-9zbMath0793.68087OpenAlexW1995334947MaRDI QIDQ1324687

Francine Blanchet-Sadri

Publication date: 26 May 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90161-9

zbMATH Keywords

decidabilitycircuit complexityEhrenfeucht-Fraïssé gamedot-depth hierarchydot-depth-two monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (7)

Polynomial closure and unambiguous product ⋮ Polynomial closure and unambiguous product ⋮ 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$ ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ A conjecture on the concatenation product ⋮ On a complete set of generators for dot-depth two

Cites Work

• First-order logic and star-free sets
• Classifying regular events in symbolic logic
• Games, equations and dot-depth two monoids
• The dot-depth hierarchy of star-free languages is infinite
• On a complete set of generators for dot-depth two
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On a complete set of generators for dot-depth two