On winning strategies in Ehrenfeucht-Fraïssé games

DOI10.1016/S0304-3975(96)00015-1MaRDI QIDQ1269907zbMATH OpenFDO

Authors Ronald Fagin, Sanjeev Arora

Publication date 22 October 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(96)00015-1

zbMATH Keywords

computational complexitydescriptive complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On winning Ehrenfeucht games and monadic NP
• Comparing the Power of Games on Graphs
• On complexity of Ehrenfeucht-Fraïssé games
• On Complexity of Ehrenfeucht-Fraïssé Games

Cites work

• An application of games to the completeness problem for formalized theories
• Degrees of acyclicity for hypergraphs and relational database schemes
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3248792 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• Monadic generalized spectra
• On monadic NP vs monadic co-NP
• On the definability of properties of finite graphs
• Reachability is harder for directed than for undirected finite graphs
• Relational queries computable in polynomial time
• Second-order and Inductive Definability on Finite Structures
• Structure and complexity of relational queries

Cited in

(24)

• The closure of monadic NP
• Shrinking games and local formulas
• On winning Ehrenfeucht games and monadic NP
• scientific article; zbMATH DE number 1678371 (Why is no real title available?)
• On winning strategies with unary quantifiers
• The Ehrenfeucht-Fraïssé method and the planted clique conjecture
• Reachability is harder for directed than for undirected finite graphs
• Games on Strings with a Limited Order Relation
• The Ehrenfeucht-Fraïssé game for paths and cycles.
• Ehrenfeucht-Fraïssé Games on Random Structures
• Locality and modular Ehrenfeucht-Fraïssé games
• scientific article; zbMATH DE number 1059242 (Why is no real title available?)
• Comparing the Power of Games on Graphs
• An Ehrenfeucht-Fraïssé class game
• Winning Strategy for the Multiplayer and Multialliance Zeckendorf Games
• scientific article; zbMATH DE number 6790166 (Why is no real title available?)
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures
• scientific article; zbMATH DE number 7676368 (Why is no real title available?)
• Comparing the power of monadic NP games
• On complexity of Ehrenfeucht-Fraïssé games
• Count-free Weisfeiler-Leman and group isomorphism
• On the descriptive complexity of groups without abelian normal subgroups
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• On the descriptive complexity of groups without abelian normal subgroups (extended abstract)

This page was built for publication: On winning strategies in Ehrenfeucht-Fraïssé games

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