On winning Ehrenfeucht games and monadic NP
- 2 May 1996
- journal article
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 79 (1) , 61-92
- https://doi.org/10.1016/0168-0072(95)00030-5
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- On monadic NP vs. monadic co-NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On winning Ehrenfeucht games and monadic NPAnnals of Pure and Applied Logic, 1996
- Logics for context-free languagesPublished by Springer Nature ,1995
- First-order spectra with one variableJournal of Computer and System Sciences, 1990
- Reachability is harder for directed than for undirected finite graphsThe Journal of Symbolic Logic, 1990
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- Second-order Ehrenfeucht games and the deciability of the second-order theory of an equivalence relationJournal of the Australian Mathematical Society, 1975
- Monadic generalized spectraMathematical Logic Quarterly, 1975