Switch to: References

Add citations

You must login to add citations.
  1. Canonization for two variables and puzzles on the square.Martin Otto - 1997 - Annals of Pure and Applied Logic 85 (3):243-282.
    We consider infinitary logic with only two variable symbols, both with and without counting quantifiers, i.e. L2 L∞ω2 and C2 L∞ω2mεω. The main result is that finite relational structures admit canonization with respect to L2 and C2: there are polynomial time com putable functors mapping finite relational structures to unique representatives of their equivalence class with respect to indistinguishability in either of these logics. In fact we exhibit in verses to the natural invariants that characterize structures up to L2- or (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • How to define a linear order on finite models.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1997 - Annals of Pure and Applied Logic 87 (3):241-267.
    We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and lower bounds (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Finite variable logics in descriptive complexity theory.Martin Grohe - 1998 - Bulletin of Symbolic Logic 4 (4):345-398.
    Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation