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

DOI10.1007/3-540-60084-1_92zbMATH Open1412.68068OpenAlexW1516182147MaRDI QIDQ4645196FDOQ4645196

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

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

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)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On monadic NP vs monadic co-NP
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Monadic generalized spectra
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• 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)