Axiomatizing Rectangular Grids with no Extra Non-unary Relations

• Autorzy: Kopczyński Eryk

Identyfikatory

DOI

10.3233/FI-2020-1966

• Języki publikacji: EN

Abstrakty

EN

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)).

Słowa kluczowe

EN

spectrum problem; planar graphs; rectangular grids; descriptive complexity; finite model theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 176, nr 2
• Strony: 129--138
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Kopczyński Eryk

• Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

Bibliografia

• [1] Scholz H. Ein ungelöstes Problem in der symbolischen Logik. Journal of Symbolic Logic, 1952. 17:160.
• [2] Durand A, Jones ND, Makowsky JA, More M. Fifty years of the spectrum problem: survey and new results. In preparation. Bulletin of Symbolic Logic, 2012. 18(4):505-553. doi:10.2178/bsl.1804020.
• [3] Fagin R. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. Complexity of computation (proc. siam-ams sympos. appl. math., new york, 1973) (Providence, R.I.) (Richard M. Karp, editor), SIAM-AMS Proceedings, vol. 7, American Mathematical Society, 1974. pp. 43-73. URL http://www.researchgate.net/publication/242608657_Generalized_first-order_spectra_and_polynomial._time_recognizable_sets.
• [4] Jones ND, Selman AL. Turing Machines and the Spectra of First-Order Formulas. Journal of Symbolic Logic, 1974. 39(1):139-150. doi:10.2307/2272354.
• [5] Dawar A, Kopczynski E. Bounded degree and planar spectra. Logical Methods in Computer Science, 2017. 13(4). doi:10.23638/LMCS-13(4:6)2017. URL https://doi.org/10.23638/LMCS-13(4:6)2017.
• [6] Kopczynski E. Computational Complexity on the Blackboard. Fundam. Inform., 2017. 152:323-339. doi:10.3233/FI-2017-1523.
• [7] Berger R. The Undecidability of the Domino Problem. American Mathematical Society, 1966. ISBN:0821812661, 9780821812662.
• [8] Jeandel E, Rao M. An aperiodic set of 11 Wang tiles. CoRR, 2015. abs/1506.06492.
• [9] Hanf W. Model-theoretic methods in the study of elementary logic. JW Addison et al. The Theory of Models, North-Holland, Amsterdam, 1965. pp. 132-145. doi:10.2307/2271017.
• [10] Atrubin AJ. A One-Dimensional Real-Time Iterative Multiplier. IEEE Transactions on Electronic Computers, 1965. EC-14(3):394-399. doi:10.1109/PGEC.1965.264145.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).