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 Symposium on Logic in Computer Science (LICS 1994)}, year = {1994}, month = {July}, pages = {10--19}, location = {Paris, France}, publisher = {IEEE Computer Society Press} }