Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18319
Title: | On the variable hierarchy of first-order spectra | Authors: | TAN, Tony Kopczynski, Eryk |
Issue Date: | 2015 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | ACM Transactions on Computational Logic, 16 (2) (Art N° 17) | 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. erykk@mimuw.edu.pl; ptony.tan@gmail.com | Keywords: | Theory;First-order spectra;bounded number of variables;nondeterministic exponential time | Document URI: | http://hdl.handle.net/1942/18319 | ISSN: | 1529-3785 | e-ISSN: | 1557-945X | DOI: | 10.1145/2733376 | ISI #: | 000353644400008 | Rights: | 2015 ACM | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
spec-k-v-final.pdf | Peer-reviewed author version | 366.9 kB | Adobe PDF | View/Open |
2733376.pdf Restricted Access | Published version | 190.14 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
1
checked on Sep 27, 2024
Page view(s)
106
checked on Sep 7, 2022
Download(s)
156
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.