Comparing the power of monadic NP games

DOI10.1007/3-540-60178-3_95MaRDI QIDQ6064292zbMATH OpenFDO

Authors Ronald Fagin

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60178-3_95

zbMATH Keywords

colored graphfine levelfinite graphoriginal gamewinning strategy

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Recommendations

• On monadic NP vs monadic co-NP
• On winning strategies in Ehrenfeucht-Fraïssé games
• On winning Ehrenfeucht games and monadic NP
• Publication:4945236
• Comparing the Power of Games on Graphs

Cites work

• An application of games to the completeness problem for formalized theories
• Comparing the Power of Games on Graphs
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• Monadic generalized spectra
• On monadic NP vs monadic co-NP
• Reachability is harder for directed than for undirected finite graphs

Cited in

(2)

• On winning Ehrenfeucht games and monadic NP
• Comparing the Power of Games on Graphs

This page was built for publication: Comparing the power of monadic NP games

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