Name
Abstract | ||
|---|---|---|
We 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 subset of N is a spectrum of a formula which has only planar models if numbers n is an element of 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 t(n), s(n) =Omega(log(n)). |
Year | DOI | Venue |
|---|---|---|
2020 | 10.3233/FI-2020-1966 | FUNDAMENTA INFORMATICAE |
Keywords | DocType | Volume |
spectrum problem, planar graphs, rectangular grids, descriptive complexity, finite model theory | Journal | 176 |
Issue | ISSN | Citations |
2 | 0169-2968 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eryk Kopczynski | 1 | 64 | 9.68 |