PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!
Tytuł artykułu

Axiomatizing Rectangular Grids with no Extra Non-unary Relations

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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)).
Wydawca
Rocznik
Strony
129--138
Opis fizyczny
Bibliogr. 10 poz., rys.
Twórcy
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-0577ad8a-9d36-4278-8715-534f90c53ea2
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.