Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Bounded degree and planar spectra

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:48:52Z
dc.abstract.enThe 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.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorKopczyński, Eryk
dc.contributor.authorDawar, Anuj
dc.date.accessioned2024-01-24T18:45:36Z
dc.date.available2024-01-24T18:45:36Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.number4
dc.description.volume13
dc.identifier.doi10.23638/LMCS-13(4:6)2017
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/102477
dc.identifier.weblinkhttps://lmcs.episciences.org/4050
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages1-21
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enspectra finite model theory planar graphs bounded degree graphs
dc.titleBounded degree and planar spectra
dc.typeJournalArticle
dspace.entity.typePublication