Logic in Computer Science (LICS 1994)

Paper: McColm's conjecture [positive elementary inductions] (at LICS 1994)

Authors: Yuri Gurevich Neil Immerman Saharon Shelah

Abstract

G. McColm (1990) conjectured that positive elementary inductions are bounded in a class K of finite structures if every (FO+LFP) formula is equivalent to a first-order formula in K. Here (FO+LFP) is the extension of first-order logic with the least fixed point operator. We disprove the conjecture. Our main results are two model-theoretic constructions, one deterministic and the other randomized, each of which refutes McColm's conjecture

BibTeX

  @InProceedings{GurevichImmermanShe-McColmsconjecturepo,
    author = 	 {Yuri Gurevich and Neil Immerman and Saharon Shelah},
    title = 	 {McColm's conjecture [positive elementary inductions]},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994},
    year =	 1994,
    editor =	 {Samson Abramsky},
    month =	 {July}, 
    pages =      {10--19},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}
  }