Axiomatizing rectangular grids with no extra non-unary relations

DOI10.3233/FI-2020-1966MaRDI QIDQ4988942zbMATH OpenFDO

Authors Eryk Kopczyński

Publication date 20 May 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.09797

zbMATH Keywords

descriptive complexityfinite model theoryplanar graphsrectangular gridsspectrum problem

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 $AsubseteqmathbbN$ is a spectrum of a formula which has only planar models if numbers $ninA$ 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)leqn$ and $t(n),s(n)=Omega(log(n))$.

Recommendations

• The Spectra of First-Order Sentences and Computational Complexity
• Bounded degree and planar spectra
• First-order spectra with one variable
• Publication:3030809
• scientific article; zbMATH DE number 2079026

Cites work

• Computational complexity on the blackboard
• Fifty years of the spectrum problem: survey and new results
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• Logical properties of random graphs from small addable classes
• The undecidability of the domino problem
• Turing machines and the spectra of first-order formulas

Cited in

(1)

• Grid structures and undecidable constraint theories

This page was built for publication: Axiomatizing rectangular grids with no extra non-unary relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4988942)