On winning Ehrenfeucht games and monadic NP
From MaRDI portal
Publication:1919539
DOI10.1016/0168-0072(95)00030-5zbMath0856.03027MaRDI QIDQ1919539
Publication date: 24 February 1997
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(95)00030-5
global strategy; winning strategy; Ehrenfeucht-Fraïssé games; fragments of second-order logic; connectivity of ordered graphs; inexpressibility in first-order logic
03B25: Decidability of theories and sets of sentences
03C13: Model theory of finite structures
03C85: Second- and higher-order model theory
Related Items
Notions of locality and their logical characterizations over finite models, One unary function says less than two in existential second order logic, A logical approach to locality in pictures languages, Zero-one \(k\)-law, Locality and modular Ehrenfeucht-Fraïssé games, The weak zero-one laws for the random distance graphs, Zero-one laws for first-order formulas with a bounded quantifier depth, On a sequence of random distance graphs subject to the zero-one law, Verifiable properties of database transactions, The closure of monadic NP, Lower bounds for invariant queries in logics with counting., Counting modulo quantifiers on finite structures, Shrinking games and local formulas, On winning Ehrenfeucht games and monadic NP, The monadic quantifier alternation hierarchy over grids and graphs, Games on Strings with a Limited Order Relation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- First-order spectra with one variable
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- On winning strategies in Ehrenfeucht-Fraïssé games
- On monadic NP vs monadic co-NP
- On winning Ehrenfeucht games and monadic 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
- Complexity classes and theories of finite models
- Monadic generalized spectra