TY - JOUR
T1 - On the strictness of the quantifier structure hierarchy in first-order logic
AU - He, Yuguo
N1 - Publisher Copyright:
© Yuguo He.
PY - 2014/11/12
Y1 - 2014/11/12
N2 - We study a natural hierarchy in first-order logic, namely the quantifier structure hierarchy, which gives a systematic classification of first-order formulas based on structural quantifier resource. We define a variant of Ehrenfeucht-Fraïssé games that characterizes quantifier classes and use it to prove that this hierarchy is strict over finite structures, using strategy compositions. Moreover, we prove that this hierarchy is strict even over ordered finite structures, which is interesting in the context of descriptive complexity.
AB - We study a natural hierarchy in first-order logic, namely the quantifier structure hierarchy, which gives a systematic classification of first-order formulas based on structural quantifier resource. We define a variant of Ehrenfeucht-Fraïssé games that characterizes quantifier classes and use it to prove that this hierarchy is strict over finite structures, using strategy compositions. Moreover, we prove that this hierarchy is strict even over ordered finite structures, which is interesting in the context of descriptive complexity.
KW - Ehrenfeucht-Fraïssé games
KW - Finite model theory
KW - Ordered structures
KW - Point-expansion
KW - Quantifier class
KW - Quantifier structure
KW - Strategy composition
UR - http://www.scopus.com/inward/record.url?scp=84916896926&partnerID=8YFLogxK
U2 - 10.2168/LMCS-10(4:3)2014
DO - 10.2168/LMCS-10(4:3)2014
M3 - Article
AN - SCOPUS:84916896926
SN - 1860-5974
VL - 10
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
IS - 4
ER -