McColm conjecture

Details McColm conjecture McColm conjecture

1994-11-15

arxiv.org/abs/math/9411235v1

Symposium on Logic in Computer Science (1994), 10--19

Mathematics

Logic

Scientific paper

Gregory McColm 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.

Affiliated with

Also associated with

No associations

Rating

McColm conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with McColm conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and McColm conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-568896