Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18320
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | TAN, Tony | - |
dc.contributor.author | Kopczynski, Eryk | - |
dc.date.accessioned | 2015-02-11T11:41:40Z | - |
dc.date.available | 2015-02-11T11:41:40Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | SIAM JOURNAL ON COMPUTING, 44(3), p. 786-818 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/1942/18320 | - |
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 show that when restricted to using only two variables, but allowing counting quantifiers, the class of spectra of first-order logic sentences is exactly the class of semilinear sets, 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.sponsorship | University of Warsaw, Warsaw 02-097, Poland (erykk@mimuw.edu.pl). This author is supported by the Polish National Science Centre Grant DEC - 2012/07/D/ST6/02435. | - |
dc.language.iso | en | - |
dc.subject.other | two-variable logic with counting; first-order spectra; regular graphs; semi-linear; Presburger arithmetic | - |
dc.title | Regular graphs and the spectra of two-variable logic with counting | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 818 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 786 | - |
dc.identifier.volume | 44 | - |
local.format.pages | 33 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | [Kopczynski, Eryk] Univ Warsaw, PL-02097 Warsaw, Poland. [Tan, Tony] Hasselt Univ, BE-3590 Diepenbeek, Belgium. [Tan, Tony] Transnat Univ Limburg, Fac Sci, BE-3590 Diepenbeek, Belgium. | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.1137/130943625 | - |
dc.identifier.isi | 000357414100007 | - |
item.validation | ecoom 2016 | - |
item.contributor | TAN, Tony | - |
item.contributor | Kopczynski, Eryk | - |
item.accessRights | Open Access | - |
item.fullcitation | TAN, Tony & Kopczynski, Eryk (2015) Regular graphs and the spectra of two-variable logic with counting. In: SIAM JOURNAL ON COMPUTING, 44(3), p. 786-818. | - |
item.fulltext | With Fulltext | - |
crisitem.journal.issn | 0097-5397 | - |
crisitem.journal.eissn | 1095-7111 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
spectra-sicomp-v2.pdf | 595.26 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
5
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
5
checked on Apr 30, 2024
Page view(s)
70
checked on Apr 26, 2023
Download(s)
146
checked on Apr 26, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.