Paper Info
Title
Bounded degree and planar spectra.
Abstract
The finite spectrum of a first-order sentence is the set of positive integers that are the sizes of its models. The class of finite spectra is known to be the same as the complexity class NE. We consider the spectra obtained by limiting models to be either planar (in the graph-theoretic sense) or by bounding the degree of elements. We show that the class of such spectra is still surprisingly rich by establishing that significant fragments of NE are included among them. At the same time, we establish non-trivial upper bounds showing that not all sets in NE are obtained as planar or bounded-degree spectra.
Year
DOI
Venue
2017
10.23638/LMCS-13(4:6)2017
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
DocType
Volume
spectra,finite model theory,planar graphs,bounded degree graphs
Journal
13
Issue
ISSN
Citations 
4
1860-5974
0
PageRank 
References 
Authors
0.34
5
2
Name
Order
Citations
PageRank
anuj dawar188377.18
Eryk Kopczynski2649.68