Regular Graphs and the Spectra of Two-Variable Logic with Counting
Journal
SIAM Journal on Computing
Journal Volume
44
Journal Issue
3
Pages
786-818
Date Issued
2015
Author(s)
Kopczynski, Eryk
TONY TAN
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 characterizations 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 characterization 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. © 2015 Society for Industrial and Applied Mathematics.
Subjects
First-order spectra; Presburger arithmetic; Regular graphs; Semilinear; Two-variable logic with counting
Other Subjects
Digital arithmetic; Formal logic; Graphic methods; First order; Presburger arithmetic; Regular graphs; Semilinear; Two-variable logic with counting; Graph theory
Type
journal article