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.accessRightsOpen Access-
item.fulltextWith Fulltext-
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.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

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.