Switch to: References

Add citations

You must login to add citations.
  1. The Semijoin Algebra and the Guarded Fragment.Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz & Jan Van den Bussche - 2005 - 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 (9 more)  
     
    Export citation  
     
    Bookmark  
  • Guards, Bounds, and Generalized Semantics.Johan van Benthem - 2005 - Journal of Logic, Language and Information 14 (3):263-279.
    Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) of first-order (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • First Order Logic Without Equality on Relativized Semantics.Amitayu Banerjee & Mohamed Khaled - 2018 - Annals of Pure and Applied Logic 169 (11):1227-1242.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Relation Algebras From Cylindric Algebras, I.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):225-266.
    We characterise the class S Ra CA n of subalgebras of relation algebra reducts of n -dimensional cylindric algebras by the notion of a ‘hyperbasis’, analogous to the cylindric basis of Maddux, and by representations. We outline a game–theoretic approximation to the existence of a representation, and how to use it to obtain a recursive axiomatisation of S Ra CA n.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables.Maarten Marx & Szabolcs Mikulás - 1999 - 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 (8 more)  
     
    Export citation  
     
    Bookmark  
  • Weakly Associative Relation Algebras with Projections.Agi Kurucz - 2009 - Mathematical Logic Quarterly 55 (2):138-153.
    Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first-order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. There has been extensive research on (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • On Notions of Representability for Cylindric-Polyadic Algebras, and a Solution to the Finitizability Problem for Quantifier Logics with Equality.Tarek Sayed Ahmed - 2015 - Mathematical Logic Quarterly 61 (6):418-477.