Graph connectivity, monadic NP and built-in relations of moderate degree

DOI10.1007/3-540-60084-1_92MaRDI QIDQ4645196zbMATH OpenOpenAlexFDO

Authors Thomas Schwentick

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_92

zbMATH Keywords

graph connectivityextension theoremwinning strategyunary relationisomorphism type

Mathematics Subject Classification ID

Applications of game theory (91A80) Model theory of finite structures (03C13) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 1086672
• scientific article; zbMATH DE number 1342209
• scientific article; zbMATH DE number 1775416
• On monadic NP vs monadic co-NP
• On winning strategies with unary quantifiers

Cites work

• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 108465 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• An application of games to the completeness problem for formalized theories
• Monadic generalized spectra
• On monadic NP vs monadic co-NP
• Reachability is harder for directed than for undirected finite graphs
• Second-order and Inductive Definability on Finite Structures
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(6)

• Lower bounds for invariant queries in logics with counting.
• The closure of monadic NP
• On winning strategies with unary quantifiers
• On monadic NP vs monadic co-NP
• scientific article; zbMATH DE number 1775416 (Why is no real title available?)
• Comparing the Power of Games on Graphs

This page was built for publication: Graph connectivity, monadic NP and built-in relations of moderate degree

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