Dawar, Anuj and Kopczyński, Eryk - Bounded degree and planar spectra

lmcs:4050 - Logical Methods in Computer Science, November 6, 2017, Volume 13, Issue 4
Bounded degree and planar spectra

Authors: Dawar, Anuj and Kopczyński, Eryk

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.


Source : oai:arXiv.org:1609.01789
DOI : 10.23638/LMCS-13(4:6)2017
Volume: Volume 13, Issue 4
Published on: November 6, 2017
Submitted on: September 8, 2016
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,03C13, 68Q19,F.4.1,F.1.3


Share

Browsing statistics

This page has been seen 25 times.
This article's PDF has been downloaded 8 times.