DocumentCode
1996863
Title
McColm´s conjecture [positive elementary inductions]
Author
Gurevich, Yuri ; Immerman, Neil ; Shelah, Saharon
Author_Institution
Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI, USA
fYear
1994
fDate
4-7 Jul 1994
Firstpage
10
Lastpage
19
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
Keywords
formal logic; finite structures; first-order formula; first-order logic; least fixed point operator; model-theoretic constructions; positive elementary inductions; Building materials; Computer science; Logic; Mathematics; Vocabulary;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science, 1994. LICS '94. Proceedings., Symposium on
Conference_Location
Paris
Print_ISBN
0-8186-6310-3
Type
conf
DOI
10.1109/LICS.1994.316091
Filename
316091
Link To Document