 |
 |
Anuj Dawar ; Eryk Kopczyński - Bounded degree and planar spectra
lmcs:2024 - Logical Methods in Computer Science, November 6, 2017, Volume 13, Issue 4 - https://doi.org/10.23638/LMCS-13(4:6)2017Bounded degree and planar spectraArticle
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: arXiv.org:1609.01789
Volume: Volume 13, Issue 4
Published on: November 6, 2017
Accepted on: October 24, 2017
Submitted on: September 8, 2016
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,03C13, 68Q19,F.4.1,F.1.3
Classifications
Consultation statistics
This page has been seen 1851 times.
This article's PDF has been downloaded 438 times.