Axiomatizing Rectangular Grids with no Extra Non-unary Relations

Issue title: Computational Intelligence and Brain Understanding

Guest editors: Kuntal Ghosh and Sushmita Mitra

Article type: Research Article

Authors: Kopczyński, Eryk^{; *}

Affiliations: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. [email protected]

Correspondence: [*] Address for correspondence: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

Abstract: We construct a first-order formula φ such that all finite models of φ 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 ⊆ ℕ is a spectrum of a formula which has only planar models if numbers n ∈ 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) = Ω(log(n)).

Keywords: spectrum problem, planar graphs, rectangular grids, descriptive complexity, finite model theory

DOI: 10.3233/FI-2020-1966

Journal: Fundamenta Informaticae, vol. 176, no. 2, pp. 129-138, 2020