On the strictness of the quantifier structure hierarchy in first-order logic
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2014-11-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/965/pdf |
| _version_ | 1797268610080571392 |
|---|---|
| author | Yuguo He |
| author_facet | Yuguo He |
| author_sort | Yuguo He |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:35:13Z |
| format | Article |
| id | doaj.art-1bc4ef70c1464ec282529f94e0478d59 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:13Z |
| publishDate | 2014-11-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-1bc4ef70c1464ec282529f94e0478d592024-03-08T09:37:57ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-11-01Volume 10, Issue 410.2168/LMCS-10(4:3)2014965On the strictness of the quantifier structure hierarchy in first-order logicYuguo HeWe 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.https://lmcs.episciences.org/965/pdfcomputer science - logic in computer science |
| spellingShingle | Yuguo He On the strictness of the quantifier structure hierarchy in first-order logic Logical Methods in Computer Science computer science - logic in computer science |
| title | On the strictness of the quantifier structure hierarchy in first-order logic |
| title_full | On the strictness of the quantifier structure hierarchy in first-order logic |
| title_fullStr | On the strictness of the quantifier structure hierarchy in first-order logic |
| title_full_unstemmed | On the strictness of the quantifier structure hierarchy in first-order logic |
| title_short | On the strictness of the quantifier structure hierarchy in first-order logic |
| title_sort | on the strictness of the quantifier structure hierarchy in first order logic |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/965/pdf |
| work_keys_str_mv | AT yuguohe onthestrictnessofthequantifierstructurehierarchyinfirstorderlogic |