Switch to: References

Add citations

You must login to add citations.
  1. Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
    The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • Second-order propositional modal logic and monadic alternation hierarchies.Antti Kuusisto - 2015 - Annals of Pure and Applied Logic 166 (1):1-28.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Truth definitions in finite models.Leszek Aleksander Kołodziejczyk - 2004 - Journal of Symbolic Logic 69 (1):183-200.
    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 (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Arity hierarchies.Martin Grohe - 1996 - Annals of Pure and Applied Logic 82 (2):103-163.
    Many logics considered in finite model theory have a natural notion of an arity. The purpose of this article is to study the hierarchies which are formed by the fragments of such logics whose formulae are of bounded arity.Based on a construction of finite graphs with a certain property of homogeneity, we develop a method that allows us to prove that the arity hierarchies are strict for several logics, including fixed-point logics, transitive closure logic and its deterministic version, variants of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • On spectra of sentences of monadic second order logic with counting.E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.
    We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Fifty years of the spectrum problem: survey and new results.Arnaud Durand, Neil D. Jones, Johann A. Makowsky & Malika More - 2012 - Bulletin of Symbolic Logic 18 (4):505-553.
    In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations