22 found
Sort by:
  1. Loredana Afanasiev, Patrick Blackburn, Ioanna Dimitriou, Bertrand Gaiffe, Evan Goris, Maarten Marx & Maarten de Rijke (2005). PDL for Ordered Trees. Journal of Applied Non-Classical Logics 15 (2):115-135.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz & Jan Van den Bussche (2005). The Semijoin Algebra and the Guarded Fragment. Journal of Logic, Language and Information 14 (3):331-343.
    In the 1970s Codd introduced the relational algebra, with operators selection, projection, union, difference and product, and showed that it is equivalent to first-order logic. In this paper, we show that if we replace in Codd’s relational algebra the product operator by the “semijoin” operator, then the resulting “semijoin algebra” is equivalent to the guarded fragment of first-order logic. We also define a fixed point extension of the semijoin algebra that corresponds to μGF.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  3. Connie Xiaokang Yu, Maria Luisa Dalla Chiara, Fraser MacBride, Dale Jacquette, Maarten Marx, Stig Alstrup Rasmussen & Sven Ove Hansson (2004). Book Reviews. [REVIEW] Studia Logica 77 (1):619-624.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Carlos Areces, Patrick Blackburn & Maarten Marx (2003). Repairing the Interpolation Theorem in Quantified Modal Logic. Annals of Pure and Applied Logic 124 (1-3):287-299.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Nick Bezhanishvili & Maarten Marx (2003). All Proper Normal Extensions of S5-Square Have the Polynomial Size Model Property. Studia Logica 73 (3):367 - 382.
    We show that every proper normal extension of the bi-modal system S5 2 has the poly-size model property. In fact, to every proper normal extension L of S5 2 corresponds a natural number b(L) - the bound of L. For every L, there exists a polynomial P(·) of degree b(L) + 1 such that every L-consistent formula is satisfiable on an L-frame whose universe is bounded by P(||), where || denotes the number of subformulas of . It is shown that (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  6. Patrick Blackburn & Maarten Marx (2003). Constructive Interpolation in Hybrid Logic. Journal of Symbolic Logic 68 (2):463-480.
    Craig's interpolation lemma (if φ → ψ is valid, then φ → θ and θ → ψ are valid, for θ a formula constructed using only primitive symbols which occur both in φ and ψ) fails for many propositional and first order modal logics. The interpolation property is often regarded as a sign of well-matched syntax and semantics. Hybrid logicians claim that modal logic is missing important syntactic machinery, namely tools for referring to worlds, and that adding such machinery solves (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  7. Patrick Blackburn & Maarten Marx (2002). Remarks on Gregory's “Actually” Operator. Journal of Philosophical Logic 31 (3):281-288.
    In this note we show that the classical modal technology of Sahlqvist formulas gives quick proofs of the completeness theorems in [8] (D. Gregory, Completeness and decidability results for some propositional modal logics containing "actually" operators, Journal of Philosophical Logic 30(1): 57-78, 2001) and vastly generalizes them. Moreover, as a corollary, interpolation theorems for the logics considered in [8] are obtained. We then compare Gregory's modal language enriched with an "actually" operator with the work of Arthur Prior now known under (...)
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  8. Eva Hoogland & Maarten Marx (2002). Interpolation and Definability in Guarded Fragments. Studia Logica 70 (3):373 - 409.
    The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  9. Maarten Marx (2002). Computing with Cylindric Modal Logics and Arrow Logics, Lower Bounds. Studia Logica 72 (2):233-252.
    The complexity of the satisfiability problems of various arrow logics and cylindric modal logics is determined. As is well known, relativising these logics makes them decidable. There are several parameters that can be set in such a relativisation. We focus on the following three: the number of variables involved, the similarity type and the kind of relativised models considered. The complexity analysis shows the importance and relevance of these parameters.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  10. Maarten Marx & Szabolcs Mikulás (2002). An Elementary Construction for a Non-Elementary Procedure. Studia Logica 72 (2):253-263.
    We consider the problem of the product finite model property for binary products of modal logics. First we give a new proof for the product finite model property of the logic of products of Kripke frames, a result due to Shehtman. Then we modify the proof to obtain the same result for logics of products of Kripke frames satisfying any combination of seriality, reflexivity and symmetry. We do not consider the transitivity condition in isolation because it leads to infinity axioms (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  11. Carlos Areces, Patrick Blackburn & Maarten Marx (2001). Hybrid Logics: Characterization, Interpolation and Complexity. Journal of Symbolic Logic 66 (3):977-1010.
    Hybrid languages are expansions of propositional modal languages which can refer to (or even quantify over) worlds. The use of strong hybrid languages dates back to at least [Pri67], but recent work (for example [BS98, BT98a, BT99]) has focussed on a more constrained system called $\mathscr{H}(\downarrow, @)$ . We show in detail that $\mathscr{H}(\downarrow, @)$ is modally natural. We begin by studying its expressivity, and provide model theoretic characterizations (via a restricted notion of Ehrenfeucht-Fraisse game, and an enriched notion of (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  12. Maarten Marx (2001). Tolerance Logic. Journal of Logic, Language and Information 10 (3):353-374.
    We expand first order models with a tolerance relation on thedomain. Intuitively, two elements stand in this relation if they arecognitively close for the agent who holds the model. This simplenotion turns out to be very powerful. It leads to a semanticcharacterization of the guarded fragment of Andréka, van Benthemand Németi, and highlights the strong analogies between modallogic and this fragment. Viewing the resulting logic – tolerance logic– dynamically it is a resource-conscious information processingalternative to classical first order logic. The (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  13. Jelle Gerbrandy, Maarten Marx, Maarten de Rijke & Yde Venema (eds.) (1999). Essays Dedicated to Johan van Benthem on the Occasion of His 50th Birthday. Amsterdam University Press.
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  14. Robin Hirsch, Ian Hodkinson, Maarten Marx, Szabolsc Mikulás & Mark Reynolds (1999). Mosaics and Step-by-Step. Remarks on “A Modal Logic of Relations”. In E. Orłowska (ed.), Logic at Work. Heidelberg.
    No categories
     
    My bibliography  
     
    Export citation  
  15. Maarten Marx (1999). The Classical Decision Problem, Egon Börger, Erich Grädel, and Yuri Gurevich. Journal of Logic, Language and Information 8 (4):478-481.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  16. Maarten Marx & Szabolcs Mikulás (1999). Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables. Journal of Symbolic Logic 64 (4):1563-1572.
    The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables (without function symbols), using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two (Pse 2 ). The new proof also shows the known results that the universal theory of Pse 2 is decidable and that every finite Pse 2 can be represented on a finite (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  17. Szabolcs Mikulás & Maarten Marx (1999). Undecidable Relativizations of Algebras of Relations. Journal of Symbolic Logic 64 (2):747-760.
    In this paper we show that relativized versions of relation set algebras and cylindric set algebras have undecidable equational theories if we include coordinatewise versions of the counting operations into the similarity type. We apply these results to the guarded fragment of first-order logic.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  18. Maarten Marx (1998). Amalgamation in Relation Algebras. Journal of Symbolic Logic 63 (2):479-484.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  19. Maarten Marx & Carlos Areces (1998). Failure of Interpolation in Combined Modal Logics. Notre Dame Journal of Formal Logic 39 (2):253-273.
    We investigate transfer of interpolation in such combinations of modal logic which lead to interaction of the modalities. Combining logics by taking products often blocks transfer of interpolation. The same holds for combinations by taking unions, a generalization of Humberstone's inaccessibility logic. Viewing first-order logic as a product of modal logics, we derive a strong counterexample for failure of interpolation in the finite variable fragments of first-order logic. We provide a simple condition stated only in terms of frames and bisimulations (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  20. Maarten Marx (1997). Multi-Dimensional Modal Logic. Kluwer Academic Publishers.
    Over the last twenty years, in all of these neighbouring fields, modal systems have been developed that we call multi-dimensional. (Our definition of multi ...
    Direct download  
     
    My bibliography  
     
    Export citation  
  21. Maarten Marx (1996). Multi-Dimensional Semantics for Modal Logics. Notre Dame Journal of Formal Logic 37 (1):25-34.
    We show that every modal logic (with arbitrary many modalities of arbitrary arity) can be seen as a multi-dimensional modal logic in the sense of Venema. This result shows that we can give every modal logic a uniform "concrete" semantics, as advocated by Henkin et al. This can also be obtained using the unravelling method described by de Rijke. The advantage of our construction is that the obtained class of frames is easily seen to be elementary and that the worlds (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  22. Maarten Marx, Szabolcs Mikul & István Németi (1995). Taming Logic. Journal of Logic, Language and Information 4 (3):207-226.
    In this paper, we introduce a general technology, calledtaming, for finding well-behaved versions of well-investigated logics. Further, we state completeness, decidability, definability and interpolation results for a multimodal logic, calledarrow logic, with additional operators such as thedifference operator, andgraded modalities. Finally, we give a completeness proof for a strong version of arrow logic.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation