Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorTAN, Tony-
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 show that when restricted to using only two variables, but allowing counting quantifiers, the spectra of first-order logic sentences are semilinear and hence, closed under complement. At the heart of our proof are semilinear characterisations for the existence of regular and biregular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices. Our proof also provides a simple characterisation of models of two-variable logic with counting -- that is, up to renaming and extending the relation names, they are simply a collection of regular and biregular graphs.-
dc.description.sponsorshipFWO Pegasus Marie Curie Fellowship-
dc.subject.othertwo-variable logic with counting; first-order spectra; regular graphs; semi-linear; Presburger arithmetic-
dc.titleRegular graphs and the spectra of two-variable logic with counting-
local.contributor.corpauthorKopczýnski, Eryk-
item.fulltextWith Fulltext-
item.accessRightsOpen Access-
item.contributorTAN, Tony-
item.fullcitationTAN, Tony (2013) Regular graphs and the spectra of two-variable logic with counting.-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
spectra-arxiv.pdf378.22 kBAdobe PDFView/Open
Show simple item record

Page view(s)

checked on Jul 3, 2022


checked on Jul 3, 2022

Google ScholarTM


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