Yuguo He - On the strictness of the quantifier structure hierarchy in first-order logic

lmcs:965 - Logical Methods in Computer Science, November 13, 2014, Volume 10, Issue 4 - https://doi.org/10.2168/LMCS-10(4:3)2014
On the strictness of the quantifier structure hierarchy in first-order logicArticle

Authors: Yuguo He

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-Fraisse 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.

Comment: 38 pages, 8 figures

https://doi.org/10.2168/LMCS-10(4:3)2014
Source: arXiv.org:1409.7488
Volume: Volume 10, Issue 4
Secondary volumes: Selected Papers of the 25th IEEE Symposium on Logic in Computer Science (LICS 2010)
Published on: November 13, 2014
Imported on: January 6, 2011
Keywords: Computer Science - Logic in Computer Science
Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Share and export

Consultation statistics

This page has been seen 3008 times.
This article's PDF has been downloaded 812 times.