Games, equations and the dot-depth hierarchy

DOI10.1016/0898-1221(89)90179-XzbMath0682.03015MaRDI QIDQ1823928

Francine Blanchet-Sadri

Publication date: 1989

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

zbMATH Keywords

monoid varietiesEhrenfeucht-Fraisse gamefine structure of the Straubing hierarchy of star-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Equational classes, universal algebra in model theory (03C05)

Related Items

On Boolean combinations forming piecewise testable languages ⋮ 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$ ⋮ Tropical representations and identities of the stylic monoid ⋮ On the word problem for syntactic monoids of piecewise testable languages. ⋮ Hierarchies of Piecewise Testable Languages ⋮ Normal forms under Simon's congruence ⋮ Games, equations and dot-depth two monoids ⋮ Equations and dot-depth one ⋮ REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT ⋮ HIERARCHIES OF PIECEWISE TESTABLE LANGUAGES ⋮ On dot-depth two ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ Equations and monoid varieties of dot-depth one and two ⋮ On a complete set of generators for dot-depth two

Cites Work

• Categories as algebra: An essential ingredient in the theory of monoids
• First-order logic and star-free sets
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Characterizations of locally testable events
• An application of games to the completeness problem for formalized theories
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• Application of model theoretic games to discrete linear orders and finite automata
• Algebraic decision procedures for local testability
• On finite monoids having only trivial subgroups
• $ℵ_0$-categoricity of linear orderings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Games, equations and the dot-depth hierarchy