The Semijoin Algebra and the Guarded Fragment

Journal of Logic, Language and Information 14 (3):331-343 (2005)
  Copy   BIBTEX

Abstract

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,271

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

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.
Guards, Bounds, and generalized semantics.Johan van Benthem - 2005 - Journal of Logic, Language and Information 14 (3):263-279.
Guarded fragments with constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic, Language and Information 14 (3):281-288.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Tolerance logic.Maarten Marx - 2001 - Journal of Logic, Language and Information 10 (3):353-374.
Multi-dimensional modal logic, Maarten Marx and Yde Venema.Michael Zakharyaschev - 2000 - Journal of Logic, Language and Information 9 (1):128-131.
Guarded fragments with constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic 14 (3):281-288.
Process algebra with four-valued logic.Jan A. Bergstra & Alban Ponse - 2000 - Journal of Applied Non-Classical Logics 10 (1):27-53.
Form and content in semantics.Y. Wilks - 1990 - Synthese 82 (3):329-51.
The classical decision problem, Egon börger, Erich grädel, and Yuri Gurevich.Maarten Marx - 1999 - Journal of Logic, Language and Information 8 (4):478-481.
The guarded fragment with transitive guards.Wiesław Szwast & Lidia Tendera - 2004 - Annals of Pure and Applied Logic 128 (1-3):227-276.
Editorial: Modal logic and dynamic semantics. [REVIEW]Yde Venema - 1997 - Journal of Logic, Language and Information 6 (4):357-360.

Analytics

Added to PP
2017-02-23

Downloads
21 (#704,955)

6 months
16 (#143,467)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Tolerance logic.Maarten Marx - 2001 - Journal of Logic, Language and Information 10 (3):353-374.

Add more references