Comparing the Power of Games on Graphs

DOI10.1002/MALQ.19970430402MaRDI QIDQ4366126zbMATH OpenOpenAlexFDO

Authors Ronald Fagin

Publication date 10 May 1998

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19970430402

zbMATH Keywords

computational complexitydescriptive complexityAjtai-Fagin gamemonadic NPEhrenfeucht-Fraïssé game

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1059242
• Comparing the power of monadic NP games
• On monadic NP vs monadic co-NP
• scientific article; zbMATH DE number 1678371
• Weak Ehrenfeucht-Fraïssé games
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• On winning strategies in Ehrenfeucht-Fraïssé games
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures
• scientific article; zbMATH DE number 1342211
• Graph connectivity, monadic NP and built-in relations of moderate degree

Cites work

• Monadic generalized spectra
• Subclasses of binary NP

Cited in

(5)

• The closure of monadic NP
• Power Indices in Spanning Connectivity Games
• The Ehrenfeucht-Fraïssé game for paths and cycles.
• Comparing the power of monadic NP games
• Verifiable properties of database transactions

This page was built for publication: Comparing the Power of Games on Graphs

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