Order:
  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  
  2.  27
    The Semijoin Algebra and the Guarded Fragment.Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz & Jan 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  
     
    Export citation  
     
    Bookmark  
  3.  22
    SO(∀∃^*) Sentences and Their Asymptotic Probabilities.Eric Rosen & Jerzy Tyszkiewicz - 2000 - Mathematical Logic Quarterly 46 (4):435-452.
    We prove a 0-1 law for the fragment of second order logic SO over parametric classes of finite structures which allow only one unary atomic type. This completes the investigation of 0-1 laws for fragments of second order logic defined in terms of first order quantifier prefixes over, e.g., simple graphs and tournaments. We also prove a low oscillation law, and establish the 0-1 law for Σ14 without any restriction on the number of unary types.
    Direct download  
     
    Export citation  
     
    Bookmark