Comparing the Power of Games on Graphs

DOI10.1002/MALQ.19970430402zbMATH Open0888.03027OpenAlexW2171521913MaRDI QIDQ4366126FDOQ4366126

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

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

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)

Cites Work

• Subclasses of binary NP
• Monadic generalized spectra

Cited In (4)

• The closure of monadic NP
• Verifiable properties of database transactions
• Comparing the power of monadic NP games
• Power Indices in Spanning Connectivity Games

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)