On winning Ehrenfeucht games and monadic NP
Author:
- Thomas SchwentickTSThomas Schwentick
- 1 May 1996
- journal article
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 79 (1) , 61-92
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- On winning Ehrenfeucht games and monadic NPAnnals of Pure and Applied Logic, 1996
- Logics for context-free languages1995
- 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
- An application of games to the completeness problem for formalized theoriesFundamenta Mathematicae, 1960