Journal of Symbolic Logic 69 (1):183-200 (2004)

The paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition. We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic ᵍ does not depend on the syntax of L, as long as it is decidable. It follows that for a natural ᵍ there exist FM-truth definitions whose evaluation is much easier than the combined complexiy of ᵍ would suggest. We apply the general theory to give a complexity-theoretical characterization of the logics for which the $\Sigma_{m}^{d}$ classes (prenex classes of higher order logics) define FM-truth. For any $d \geq 2.m \geq 1$ we construct a family $\{[\Sigma_{m}^{d}]^{\leg\kappa}\}\kappa\in\omega$ of syntactically defined fragments of $\Sigma_{m}^{d}$ which satisfy this characterization. We also use the $[\Sigma_{m}^{d}]\leg\kappa$ classes to give a refinement of known results on the complexity classes captured by $\Sigma_{m}^{d}$ . We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary $\sigma$ , of a fixed number $\kappa$ such that model checking for all first order sentences over $\sigma$ can be done in deterministic time $n^{\kappa}$
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1080938836
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,634
Through your library

References found in this work BETA

Arity and Alternation in Second-Order Logic.J. A. Makowsky & Y. B. Pnueli - 1996 - Annals of Pure and Applied Logic 78 (1-3):189-202.
On Representing Concepts in Finite Models.Marcin Mostowski - 2001 - Mathematical Logic Quarterly 47 (4):513-523.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

What Were Tarski's Truth-Definitions For?John F. Fox - 1989 - History and Philosophy of Logic 10 (2):165-179.
The Concept of Truth in a Finite Universe.Panu Raatikainen - 2000 - Journal of Philosophical Logic 29 (6):617-633.
Fixed Point Logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.


Added to PP index

Total views
209 ( #41,068 of 2,348,958 )

Recent downloads (6 months)
1 ( #512,628 of 2,348,958 )

How can I increase my downloads?


My notes