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

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• Comparing the power of monadic NP games 👍 👎
• On monadic NP vs monadic co-NP 👍 👎
• Title not available (Why is that?) 👍 👎
• Weak Ehrenfeucht-Fraïssé games 👍 👎
• On the Ehrenfeucht-Fraïssé game in theoretical computer science 👍 👎
• On winning strategies in Ehrenfeucht-Fraïssé games 👍 👎
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures 👍 👎
• Title not available (Why is that?) 👍 👎
• Graph Connectivity, Monadic NP and built-in relations of moderate degree 👍 👎

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)