Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/18319
Full metadata record
DC FieldValueLanguage
dc.contributor.authorTAN, Tony-
dc.contributor.authorKopczynski, Eryk-
dc.date.accessioned2015-02-11T11:38:28Z-
dc.date.available2015-02-11T11:38:28Z-
dc.date.issued2015-
dc.identifier.citationACM Transactions on Computational Logic, 16 (2) (Art N° 17)-
dc.identifier.issn1529-3785-
dc.identifier.urihttp://hdl.handle.net/1942/18319-
dc.description.abstractThe 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.sponsorshipThe 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.isoen-
dc.publisherASSOC COMPUTING MACHINERY-
dc.rights2015 ACM-
dc.subject.otherTheory-
dc.subject.otherFirst-order spectra-
dc.subject.otherbounded number of variables-
dc.subject.othernondeterministic exponential time-
dc.titleOn the variable hierarchy of first-order spectra-
dc.typeJournal Contribution-
dc.identifier.issue2-
dc.identifier.volume16-
local.format.pages13-
local.bibliographicCitation.jcatA1-
dc.description.notesKopczynski, E (reprint author), Univ Warsaw, PL-00325 Warsaw, Poland. erykk@mimuw.edu.pl; ptony.tan@gmail.com-
local.publisher.place1601 Broadway, 10th Floor, NEW YORK, NY 10019-7434-
local.type.refereedRefereed-
local.type.specifiedArticle-
local.bibliographicCitation.artnr17-
dc.identifier.doi10.1145/2733376-
dc.identifier.isi000353644400008-
dc.identifier.eissn1557-945X-
local.uhasselt.internationalyes-
item.contributorTAN, Tony-
item.contributorKopczynski, Eryk-
item.fullcitationTAN, Tony & Kopczynski, Eryk (2015) On the variable hierarchy of first-order spectra. In: ACM Transactions on Computational Logic, 16 (2) (Art N° 17).-
item.accessRightsOpen Access-
item.fulltextWith Fulltext-
item.validationecoom 2016-
crisitem.journal.issn1529-3785-
crisitem.journal.eissn1557-945X-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
spec-k-v-final.pdfPeer-reviewed author version366.9 kBAdobe PDFView/Open
2733376.pdf
  Restricted Access		Published version190.14 kBAdobe PDFView/Open    Request a copy
Show simple item record

SCOPUSTM   
Citations

1
checked on Sep 3, 2020

WEB OF SCIENCETM
Citations

1
checked on Apr 30, 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.