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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.