On the Ehrenfeucht-Fraïssé game in theoretical computer science

DOI10.1007/3-540-56610-4_89zbMath1497.03049OpenAlexW2172111426MaRDI QIDQ5044763

Wolfgang Thomas

Publication date: 2 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56610-4_89

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Basic properties of first-order languages and structures (03C07)

Related Items

Parity game reductions, First-order logic on finite trees, Simulation relations and applications in formal methods, Undecidability of domino games and hhp-bisimilarity., Complexity of Weak Bisimilarity and Regularity for BPA and BPP, On the computational complexity of bisimulation, redux, Deciding bisimulation-like equivalences with finite-state processes, Expressive power of existential first-order sentences of Büchi's sequential calculus, AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS, Unnamed Item, An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic

Cites Work

• Definability with bounded number of bound variables
• Upper and lower bounds for first order expressibility
• The monadic theory of order
• An application of games to the completeness problem for formalized theories
• Rabin's uniformization problem
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• Algebraic laws for nondeterminism and concurrency
• A spectrum hierarchy
• Application of model theoretic games to discrete linear orders and finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item