Switch to: References

Add citations

You must login to add citations.
  1. Expressive Completeness Through Logically Tractable Models.Martin Otto - 2013 - Annals of Pure and Applied Logic 164 (12):1418-1453.
    How can we prove that some fragment of a given logic has the power to define precisely all structural properties that satisfy some characteristic semantic preservation condition? This issue is a fundamental one for classical model theory and applications in non-classical settings alike. While methods differ greatly, and while the classical methods can usually not be matched for instance in the setting of finite model theory, this note surveys some interesting commonality revolving around the use and availability of tractable representatives (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Bisimulation and Coverings for Graphs and Hypergraphs.Martin Otto - 2013 - In Kamal Lodaya (ed.), Logic and its Applications. Springer. pp. 5--16.
  • Modal Logic: A Semantic Perspective.Patrick Blackburn & Johan van Benthem - 1988 - Ethics 98:501-517.
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 BASIC MODAL LOGIC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  • Some Model Theory of Guarded Negation.Vince Bárány, Michael Benedikt & Balder ten Cate - 2018 - Journal of Symbolic Logic 83 (4):1307-1344.
    The Guarded Negation Fragment is a fragment of first-order logic that contains all positive existential formulas, can express the first-order translations of basic modal logic and of many description logics, along with many sentences that arise in databases. It has been shown that the syntax of GNFO is restrictive enough so that computational problems such as validity and satisfiability are still decidable. This suggests that, in spite of its expressive power, GNFO formulas are amenable to novel optimizations. In this article (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • A Generalization of the Łoś–Tarski Preservation Theorem.Abhisekh Sankaran, Bharat Adsul & Supratik Chakraborty - 2016 - Annals of Pure and Applied Logic 167 (3):189-210.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  • The Finite Model Property for Logics with the Tangle Modality.Robert Goldblatt & Ian Hodkinson - 2018 - Studia Logica 106 (1):131-166.
    The tangle modality is a propositional connective that extends basic modal logic to a language that is expressively equivalent over certain classes of finite frames to the bisimulation-invariant fragments of both first-order and monadic second-order logic. This paper axiomatises several logics with tangle, including some that have the universal modality, and shows that they have the finite model property for Kripke frame semantics. The logics are specified by a variety of conditions on their validating frames, including local and global connectedness (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Some Aspects of Model Theory and Finite Structures.Eric Rosen - 2002 - Bulletin of Symbolic Logic 8 (3):380-403.
  • Modal and Guarded Characterisation Theorems Over Finite Transition Systems.Martin Otto - 2004 - Annals of Pure and Applied Logic 130 (1-3):173-205.
    We explore the finite model theory of the characterisation theorems for modal and guarded fragments of first-order logic over transition systems and relational structures of width two. A new construction of locally acyclic bisimilar covers provides a useful analogue of the well known tree-like unravellings that can be used for the purposes of finite model theory. Together with various other finitary bisimulation respecting model transformations, and Ehrenfeucht–Fraïssé game arguments, these covers allow us to upgrade finite approximations for full bisimulation equivalence (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • On Preservation Theorems for Two-Variable Logic.Erich Gradel & Eric Rosen - 1999 - Mathematical Logic Quarterly 45 (3):315-325.
    We show that the existential preservation theorem fails for two-variable first-order logic FO2. It is known that for all k ≥ 3, FOk does not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds for FO2.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Modal Characterisation Theorems Over Special Classes of Frames.Anuj Dawar & Martin Otto - 2009 - Annals of Pure and Applied Logic 161 (1):1-42.
    We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   10 citations