On winning Ehrenfeucht games and monadic NP

DOI10.1016/0168-0072(95)00030-5zbMath0856.03027OpenAlexW2025800967MaRDI QIDQ1919539

Thomas Schwentick

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

zbMATH Keywords

global strategywinning strategyEhrenfeucht-Fraïssé gamesfragments of second-order logicconnectivity of ordered graphsinexpressibility in first-order logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85)

Related Items (18)

Shrinking games and local formulas ⋮ One unary function says less than two in existential second order logic ⋮ A logical approach to locality in pictures languages ⋮ On winning Ehrenfeucht games and monadic NP ⋮ The weak zero-one laws for the random distance graphs ⋮ Nonstandard methods for finite structures ⋮ Zero-one \(k\)-law ⋮ Locality and modular Ehrenfeucht-Fraïssé games ⋮ Zero-one laws for first-order formulas with a bounded quantifier depth ⋮ Games on Strings with a Limited Order Relation ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Notions of locality and their logical characterizations over finite models ⋮ On a sequence of random distance graphs subject to the zero-one law ⋮ Verifiable properties of database transactions ⋮ The closure of monadic NP ⋮ On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra ⋮ Lower bounds for invariant queries in logics with counting. ⋮ Counting modulo quantifiers on finite structures

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

This page was built for publication: On winning Ehrenfeucht games and monadic NP