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

DOI10.24033/MSMF.309MaRDI QIDQ3347321zbMATHOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 515730
• An Ehrenfeucht-Fraïssé game for inquisitive first-order logic
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• An extension of the Ehrenfeucht-Fraïssé game for first order logics augmented with Lindström quantifiers
• scientific article; zbMATH DE number 1086492
• scientific article; zbMATH DE number 1678371
• An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic
• scientific article; zbMATH DE number 761274
• Ehrenfeucht-Fraïssé games in finite set theory
• Languages versus \(\omega\)-languages in regular infinite games

Cites work

• scientific article; zbMATH DE number 4037246 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3892608 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3390700 (Why is no real title available?)
• A generalization of the Schützenberger product of finite monoids
• Classifying regular events in symbolic logic
• Dot-depth of star-free events
• The dot-depth hierarchy of star-free languages is infinite

Cited in

(21)

• Semigroups and languages of dot-depth two
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• Languages of dot-depth 3/2
• On dot-depth two
• On a complete set of generators for dot-depth two
• A conjecture on the concatenation product
• Hierarchies and reducibilities on regular languages related to modulo counting
• Trees, congruences and varieties of finite semigroups
• Semantics of attack-defense trees for dynamic countermeasures and a new hierarchy of star-free languages
• Inclusion relations between some congruences related to the dot-depth hierarchy
• Equations and monoid varieties of dot-depth one and two
• On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids
• Games, equations and the dot-depth hierarchy
• The product of rational languages
• Classifying regular languages by a split game
• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Generic results for concatenation hierarchies
• Languages polylog-time reducible to dot-depth 1/2
• A domain-specific language for experimental game theory
• scientific article; zbMATH DE number 4049066 (Why is no real title available?)
• Games, equations and dot-depth two monoids

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)