On a complete set of generators for dot-depth two

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

Francine Blanchet-Sadri

Publication date: 26 May 1994

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

zbMATH Keywords

decidability; circuit complexity; Ehrenfeucht-Fraïssé game; dot-depth hierarchy; dot-depth-two monoids

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03B25: Decidability of theories and sets of sentences

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Polynomial closure and unambiguous product, Equations on the semidirect product of a finite semilattice by a $\mathcal {J}$-trivial monoid of height $k$, On a complete set of generators for dot-depth two, Polynomial closure and unambiguous product, Inclusion relations between some congruences related to the dot-depth hierarchy, On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids, A conjecture on the concatenation product

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