Axiomatizing Rectangular Grids with no Extra Non-unary Relations

DOI10.3233/FI-2020-1966zbMath1497.68226arXiv1912.09797MaRDI QIDQ4988942

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

planar graphsspectrum problemfinite model theorydescriptive complexityrectangular grids

Mathematics Subject Classification ID

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

Cites Work

• Computational Complexity on the Blackboard
• Turing machines and the spectra of first-order formulas
• Fifty years of the spectrum problem: survey and new results
• Logical properties of random graphs from small addable classes
• The undecidability of the domino problem
• Unnamed Item

This page was built for publication: Axiomatizing Rectangular Grids with no Extra Non-unary Relations