Logic in Computer Science (LICS 1999)

Paper: First-Order Logic vs. Fixed-Point Logic in Finite Set Theory (at LICS 1999)

Authors: Albert Atserias Phokion G. Kolaitis

Abstract

The ordered conjecture states that least fixed-point logic LFP is strictly more expressive than first-order logic FO on every infinite class of ordered finite structures. It has been established that either way of settling this conjecture would resolve open problems in complexity theory. In fact, this holds true even for the particular instance of the ordered conjecture on the class of BIT-structures, that is, ordered finite structures with a built-in BIT predicate. Using a well known isomorphism from the natural numbers to the hereditarily finite sets that maps BIT to the membership relation between sets, the ordered conjecture on BIT-structures can be translated to the problem of comparing the expressive power of FO and LFP in the context of finite set theory. The advantage of this approach is that we can use set-theoretic concepts and methods to identify certain fragments of LFP for which the restriction of the ordered conjecture is already hard to settle, as well as other restricted fragments of LFP that actually collapse to FO. These results advance the state of knowledge about the ordered conjecture on BIT-structures and contribute to the delineation of the boundary where this conjecture becomes hard to settle.

BibTeX

  @InProceedings{AtseriasKolaitis-FirstOrderLogicvsFi,
    author = 	 {Albert Atserias and Phokion G. Kolaitis},
    title = 	 {First-Order Logic vs. Fixed-Point Logic in Finite Set Theory},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999},
    year =	 1999,
    editor =	 {Giuseppe Longo},
    month =	 {July}, 
    pages =      {275--284},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }