The closure of monadic NP
From MaRDI portal
Publication:1577017
DOI10.1006/jcss.1999.1691zbMath0958.68069OpenAlexW2031470081MaRDI QIDQ1577017
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
Publication date: 27 August 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/385fd2abde8814062580dfaf6e2da7742f8937d0
Related Items (4)
Parameterized complexity classes beyond para-NP ⋮ Monadic Second Order Logic And Its Fragments ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ On the expressive power of monadic least fixed point logic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
- On the definability of properties of finite graphs
- On truth-table reducibility to SAT
- \(P_ 4\)-trees and substitution decomposition
- Some simplified NP-complete graph problems
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- On winning strategies in Ehrenfeucht-Fraïssé games
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- On monadic NP vs monadic co-NP
- On winning Ehrenfeucht games and monadic NP
- Arity and alternation in second-order logic
- An application of games to the completeness problem for formalized theories
- Reachability is harder for directed than for undirected finite graphs
- Bounded Query Classes
- Second-order and Inductive Definability on Finite Structures
- The Boolean Hierarchy I: Structural Properties
- Monadic generalized spectra
- Comparing the Power of Games on Graphs
- Subclasses of binary NP
- Graph Connectivity, Monadic NP and built-in relations of moderate degree
This page was built for publication: The closure of monadic NP
