Graph Connectivity, Monadic NP and built-in relations of moderate degree

DOI10.1007/3-540-60084-1_92zbMath1412.68068OpenAlexW1516182147MaRDI QIDQ4645196

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40) Descriptive complexity and finite models (68Q19)

Related Items (2)

The closure of monadic NP ⋮ Lower bounds for invariant queries in logics with counting.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On monadic NP vs monadic co-NP
• An application of games to the completeness problem for formalized theories
• Reachability is harder for directed than for undirected finite graphs
• Second-order and Inductive Definability on Finite Structures
• Monadic generalized spectra

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