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

Axiomatizing Rectangular Grids with no Extra Non-unary Relations

Uproszczony widok
dc.abstract.enWe construct a first-order formula phi such that all finite models of phi are non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set A subseteq N is a spectrum of a formula which has only planar models if numbers n in A can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time t(n) and space s(n), where t(n)s(n) <= n and $(n),s(n) = Omega(log(n)).
dc.affiliationUniwersytet Warszawski
dc.contributor.authorKopczyński, Eryk
dc.date.accessioned2024-01-24T16:59:48Z
dc.date.available2024-01-24T16:59:48Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.description.number2
dc.description.volume176
dc.identifier.doi10.3233/FI-2020-1966
dc.identifier.issn0169-2968
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101398
dc.identifier.weblinkhttps://content.iospress.com/download?id=10.3233/FI-2020-1966
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofFundamenta Informaticae
dc.relation.pages129-138
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleAxiomatizing Rectangular Grids with no Extra Non-unary Relations
dc.typeJournalArticle
dspace.entity.typePublication