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

DOI10.24033/MSMF.309zbMATH Open0558.68064OpenAlexW2275471570MaRDI QIDQ3347321FDOQ3347321

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) Automata and formal grammars in connection with logical questions (03D05) Model theory (03C99)

Cites Work

• Classifying regular events in symbolic logic
• A generalization of the Schützenberger product of finite monoids
• Dot-depth of star-free events
• The dot-depth hierarchy of star-free languages is infinite
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (20)

• Perfect correspondences between dot-depth and polynomial-time hierarchies
• On dot-depth two
• On the Ehrenfeucht-Fraïssé game in theoretical computer science
• Hierarchies and reducibilities on regular languages related to modulo counting
• A domain-specific language for experimental game theory
• Games, equations and dot-depth two monoids
• Inclusion relations between some congruences related to the dot-depth hierarchy
• Trees, congruences and varieties of finite semigroups
• The product of rational languages
• Generic results for concatenation hierarchies
• Classifying regular languages by a split game
• Languages polylog-time reducible to dot-depth 1/2
• Semigroups and languages of dot-depth two
• 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
• A conjecture on the concatenation product
• Languages of dot-depth 3/2
• On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids
• Semantics of attack-defense trees for dynamic countermeasures and a new hierarchy of star-free languages

   Recommendations

• Title not available (Why is that?) 👍 👎
• An Ehrenfeucht-Fraïssé game for inquisitive first-order logic 👍 👎
• On the Ehrenfeucht-Fraïssé game in theoretical computer science 👍 👎
• An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic 👍 👎
• Title not available (Why is that?) 👍 👎
• Ehrenfeucht-Fraïssé games in finite set theory 👍 👎
• LANGUAGES VERSUS ω-LANGUAGES IN REGULAR INFINITE GAMES 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347321)