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)2017
Bounded degree and planar spectraArticle

Authors: Anuj Dawar ; Eryk Kopczyński

    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.


    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

    Consultation statistics

    This page has been seen 1292 times.
    This article's PDF has been downloaded 375 times.