Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||On the variable hierarchy of first-order spectra|
|Authors: ||TAN, Tony|
|Issue Date: ||2015|
|Citation: ||ACM Transactions on Computational Logic, 16 (2)|
|Abstract: ||The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variable.
We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations.|
|Notes: ||Kopczynski, E (reprint author), Univ Warsaw, PL-00325 Warsaw, Poland.
|ISI #: ||000353644400008|
|Type: ||Journal Contribution|
|Validation: ||ecoom, 2016|
|Appears in Collections: ||Research publications|
Files in This Item:
|article||366.9 kB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.