Logic in Computer Science (LICS 1989)

Paper: Fixpoint extensions of first-order logic and datalog-like languages (at LICS 1989)

Authors: Abiteboul, S. Vianu, V.

Abstract

Datalog extensions with fixpoint semantics motivated by database queries and updates are studied. The authors suggest nontrivial fixpoint extensions of first-order logic with nondeterministic and/or noninflationary semantics. Certain properties of the language FO+IFP, such as the collapse of the hierarchy (based on the nesting of fixpoints) or the existential normal form, hold for these various logics. Their expressive power is characterized

BibTeX

  @InProceedings{AbiteboulVianu-Fixpointextensionso,
    author = 	 {Abiteboul, S. and Vianu, V.},
    title = 	 {Fixpoint extensions of first-order logic and datalog-like languages },
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {71--79},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }