Switch to: References

Add citations

You must login to add citations.
  1. A Finite Model-Theoretical Proof Of A Property Of Bounded Query Classes Within Ph.Leszek Aleksander Kołodziejczyk - 2004 - Journal of Symbolic Logic 69 (4):1105-1116.
    We use finite model theory to prove:Let m ≥ 2. Then: If there exists k such that NP ⊆ σmTIME ∩ ΠmTIME, then for every r there exists kr such that PNP[nr] ⊆ σmTIME ∩ ΠmTIME; If there exists a superpolynomial time-constructible function f such that NTIME ⊆ Σpm ∪ Πpm, then additionally PNP[nr] ⊈ Σpm ∪ Πpm.This strengthens a result by Mocas [M96] that for any r, PNP[nr] ⊈ NEXP.In addition, we use FM-truth definitions to give a simple sufficient (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  • 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  
  • Theories of Arithmetics in Finite Models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
    We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ₂—theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ₁—theory of multiplication and order is decidable in finite models as well (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations