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

DOI10.24033/msmf.309zbMath0558.68064MaRDI 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 hierarchy; star-free languages; prefix types of first order formulas

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03C99: Model theory

03D05: Automata and formal grammars in connection with logical questions

Related Items

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

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