On winning Ehrenfeucht games and monadic NP

DOI10.1016/0168-0072(95)00030-5zbMath0856.03027MaRDI 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 strategy; winning strategy; Ehrenfeucht-Fraïssé games; fragments of second-order logic; connectivity of ordered graphs; inexpressibility in first-order logic

Mathematics Subject Classification ID

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, 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