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

A note on first-order spectra with binary relations

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:03:51Z
dc.abstract.enThe spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence Φ, there is a sentence Φ′ that uses the same number of variables, but only one symmetric binary relation, such that its spectrum is linearly proportional to the spectrum of Φ. Moreover, the models of Φ′ are all bipartite graphs. As a corollary, we obtain that to settle Asser's conjecture, i.e., whether the class of spectra is closed under complement, it is sufficient to consider only sentences using only three variables whose models are restricted to undirected bipartite graphs.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorKopczyński, Eryk
dc.contributor.authorTan, Tony
dc.date.accessioned2024-01-24T18:04:26Z
dc.date.available2024-01-24T18:04:26Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.description.number2
dc.description.volume14
dc.identifier.doi10.23638/LMCS-14(2:4)2018
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101745
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages1-15
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleA note on first-order spectra with binary relations
dc.typeJournalArticle
dspace.entity.typePublication