Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18319
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | TAN, Tony | - |
dc.contributor.author | Kopczynski, Eryk | - |
dc.date.accessioned | 2015-02-11T11:38:28Z | - |
dc.date.available | 2015-02-11T11:38:28Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | ACM Transactions on Computational Logic, 16 (2) (Art N° 17) | - |
dc.identifier.issn | 1529-3785 | - |
dc.identifier.uri | http://hdl.handle.net/1942/18319 | - |
dc.description.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. | - |
dc.description.sponsorship | The first author is supported by the Polish National Science Centre grant DEC 2012/07/D/ST6/02435. The second author is supported by FWO Pegasus Marie Curie fellowship. | - |
dc.language.iso | en | - |
dc.publisher | ASSOC COMPUTING MACHINERY | - |
dc.rights | 2015 ACM | - |
dc.subject.other | Theory | - |
dc.subject.other | First-order spectra | - |
dc.subject.other | bounded number of variables | - |
dc.subject.other | nondeterministic exponential time | - |
dc.title | On the variable hierarchy of first-order spectra | - |
dc.type | Journal Contribution | - |
dc.identifier.issue | 2 | - |
dc.identifier.volume | 16 | - |
local.format.pages | 13 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Kopczynski, E (reprint author), Univ Warsaw, PL-00325 Warsaw, Poland. erykk@mimuw.edu.pl; ptony.tan@gmail.com | - |
local.publisher.place | 1601 Broadway, 10th Floor, NEW YORK, NY 10019-7434 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.bibliographicCitation.artnr | 17 | - |
dc.identifier.doi | 10.1145/2733376 | - |
dc.identifier.isi | 000353644400008 | - |
dc.identifier.eissn | 1557-945X | - |
local.uhasselt.international | yes | - |
item.fullcitation | TAN, Tony & Kopczynski, Eryk (2015) On the variable hierarchy of first-order spectra. In: ACM Transactions on Computational Logic, 16 (2) (Art N° 17). | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2016 | - |
item.contributor | TAN, Tony | - |
item.contributor | Kopczynski, Eryk | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 1529-3785 | - |
crisitem.journal.eissn | 1557-945X | - |
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.