An application of the Ehrenfeucht-Fraisse game in formal language theory

DOI10.24033/msmf.309zbMath0558.68064OpenAlexW2275471570MaRDI QIDQ3347321

Wolfgang Thomas

Publication date: 1984

Published in: Mémoires de la Société mathématique de France (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=MSMF_1984_2_16__11_0

zbMATH Keywords

dot-depth hierarchystar-free languagesprefix types of first order formulas

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Model theory (03C99) Automata and formal grammars in connection with logical questions (03D05)

Related Items (18)

On the Ehrenfeucht-Fraïssé game in theoretical computer science ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Semigroups and languages of dot-depth two ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ The product of rational languages ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Games, equations and dot-depth two monoids ⋮ Languages of dot-depth 3/2 ⋮ On dot-depth two ⋮ Classifying regular languages by a split game ⋮ Trees, congruences and varieties of finite semigroups ⋮ Generic results for concatenation hierarchies ⋮ Games, equations and the dot-depth hierarchy ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ Equations and monoid varieties of dot-depth one and two ⋮ A conjecture on the concatenation product ⋮ On a complete set of generators for dot-depth two

Cites Work

• A generalization of the Schützenberger product of finite monoids
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Dot-depth of star-free events
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An application of the Ehrenfeucht-Fraisse game in formal language theory