On winning strategies in Ehrenfeucht-Fraïssé games

DOI10.1016/S0304-3975(96)00015-1zbMath0903.68079MaRDI QIDQ1269907

Ronald Fagin

Publication date: 22 October 1998

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

zbMATH Keywords

computational complexitydescriptive complexity

Mathematics Subject Classification ID

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

Related Items (5)

On winning Ehrenfeucht games and monadic NP ⋮ Locality and modular Ehrenfeucht-Fraïssé games ⋮ On complexity of Ehrenfeucht-Fraïssé games ⋮ Games on Strings with a Limited Order Relation ⋮ The closure of monadic NP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the definability of properties of finite graphs
• Structure and complexity of relational queries
• On monadic NP vs monadic co-NP
• Degrees of acyclicity for hypergraphs and relational database schemes
• An application of games to the completeness problem for formalized theories
• Reachability is harder for directed than for undirected finite graphs
• Relational queries computable in polynomial time
• Second-order and Inductive Definability on Finite Structures
• Monadic generalized spectra

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