On monadic NP vs monadic co-NP
From MaRDI portal
Publication:1898480
DOI10.1006/inco.1995.1100zbMath0835.68046OpenAlexW1993953362MaRDI QIDQ1898480
Moshe Y. Vardi, Ronald Fagin, Larry J. Stockmeyer
Publication date: 17 September 1995
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1995.1100
Related Items
On second-order generalized quantifiers and finite structures, One unary function says less than two in existential second order logic, A logical approach to locality in pictures languages, Existential MSO over two successors is strictly weaker than over linear orders, The complexity of model checking multi-stack systems, Query languages for bags and aggregate functions, Can datalog be approximated?, On winning Ehrenfeucht games and monadic NP, Solutions and query rewriting in data exchange, The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture, Extensions of MSO and the monadic counting hierarchy, Comparing the power of monadic NP games, Indistinguishability and First-Order Logic, Expressive power of SQL., Tree-width and the monadic quantifier hierarchy., Incremental recomputation in local languages., Locality and modular Ehrenfeucht-Fraïssé games, An optimal construction of Hanf sentences, On the locality of arb-invariant first-order formulas with modulo counting quantifiers, Successor-Invariant First-Order Logic on Classes of Bounded Degree, A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\), Graph Connectivity, Monadic NP and built-in relations of moderate degree, Finite-model theory -- A personal perspective, Game-based notions of locality over finite models, Data exchange: semantics and query answering, The monadic quantifier alternation hierarchy over grids and graphs, Notions of locality and their logical characterizations over finite models, A technique for proving decidability of containment and equivalence of linear constraint queries, On winning strategies in Ehrenfeucht-Fraïssé games, Arity bounds in first-order incremental evaluation and definition of polynomial time database queries, Verifiable properties of database transactions, Local properties of query languages, The closure of monadic NP, On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra, Querying spatial databases via topological invariants, Lower bounds for invariant queries in logics with counting., Counting modulo quantifiers on finite structures, An explicit construction of graphs of bounded degree that are far from being Hamiltonian
