Axiomatizing Rectangular Grids with no Extra Non-unary Relations
| Autor: | Eryk Kopczynski |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Algebra and Number Theory Unary operation Binary relation Spectrum (functional analysis) Space (mathematics) Grid Omega Cellular automaton Logic in Computer Science (cs.LO) 68Q19 Theoretical Computer Science Combinatorics Turing machine symbols.namesake Computational Theory and Mathematics symbols F.4.0 Information Systems Mathematics |
| Zdroj: | Fundamenta Informaticae. 176:129-138 |
| ISSN: | 1875-8681 0169-2968 |
| DOI: | 10.3233/fi-2020-1966 |
| Popis: | We construct a formula $\phi$ which axiomatizes 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 \mathbb{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) \leq n$ and $t(n),s(n) = \Omega(\log(n))$. Comment: 9 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|