LIPIcs.STACS.2020.26.pdf
- Filesize: 0.51 MB
- 15 pages
Document
Domino Problem Under Horizontal Constraints
Authors
-
Part of:
Volume:
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-03-04
Cite As Get BibTex
Nathalie Aubrun, Julien Esnay, and Mathieu Sablik. Domino Problem Under Horizontal Constraints. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.26
Abstract
The Domino Problem on ℤ² asks if it is possible to tile the plane with a given set of Wang tiles; it is a classical decision problem which is known to be undecidable. The purpose of this article is to parameterize this problem to explore the frontier between decidability and undecidability. To do so we fix some horizontal constraints H on the tiles and consider a new Domino Problem DP_H: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DP_H is decidable using graphs combinatorics.
Subject Classification
ACM Subject Classification
- Theory of computation → Models of computation
- Mathematics of computing → Combinatoric problems
Keywords
- Dynamical Systems
- Symbolic Dynamics
- Subshifts
- Wang tiles
- Undecidability
- Domino Problem
- Combinatorics
- Tilings
- Subshifts of Finite Type
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Nathalie Aubrun, Sebastián Barbieri, and Emmanuel Jeandel. About the Domino Problem for Subshifts on Groups, chapter 9, pages 331-389. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-319-69152-7_9.
- Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot. The domino problem is undecidable on surface groups. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, pages 46:1-46:14, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.46.
- Nathalie Aubrun and Mathieu Sablik. Simulation of Effective Subshifts by Two-dimensional Subshifts of Finite Type. Acta Appl. Math., 126:35-63, 2013. URL: https://doi.org/10.1007/s10440-013-9808-5.
- Sebastián Barbieri and Mathieu Sablik. The domino problem for self-similar structures. In Pursuit of the universal, volume 9709 of Lecture Notes in Comput. Sci., pages 205-214. Springer, [Cham], 2016. URL: https://doi.org/10.1007/978-3-319-40189-8_21.
-
Robert Berger. Undecidability of the Domino Problem, volume 66 of Memoirs AMS. American Mathematical Society, 1966.
- David B. Cohen. The large scale geometry of strongly aperiodic subshifts of finite type. ArXiv e-prints, December 2014. URL: http://arxiv.org/abs/1412.4572.
- David B. Cohen and Chaim Goodman-Strauss. Strongly aperiodic subshifts on surface groups. ArXiv e-prints, October 2015. URL: http://arxiv.org/abs/1510.06439.
- Bruno Durand, Andrei E. Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications. J. Comput. Syst. Sci., 78(3):731-764, 2012. URL: https://doi.org/10.1016/j.jcss.2011.11.001.
-
Silvère Gangloff and Mathieu Sablik. Simulation of minimal effective dynamical systems on the cantor sets by minimal tridimensional subshifts of finite type. Prépublication (http://arxiv.org/abs/1806.07799), 2018.
- Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones mathematicae, 176(1):131, December 2008. URL: https://doi.org/10.1007/s00222-008-0161-7.
-
Emanuel Jeandel. Aperiodic subshifts of finite type on groups. https://hal.inria.fr/hal-01110211, 2015.
- Emmanuel Jeandel and Michaël Rao. An aperiodic set of 11 wang tiles. CoRR, abs/1506.06492, 2015. URL: http://arxiv.org/abs/1506.06492.
- Emmanuel Jeandel and Nicolas Rolin. Fixed parameter undecidability for wang tilesets. In Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA & JAC 2012, La Marana, Corsica, September 19-21, 2012., pages 69-85, 2012. URL: https://doi.org/10.4204/EPTCS.90.6.
- Jarkko Kari. The tiling problem revisited (extended abstract). In Jérôme Durand-Lose and Maurice Margenstern, editors, Machines, Computations, and Universality, pages 72-79, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-540-74593-8_6.
- Jarkko Kari and Etienne Moutot. Decidability and periodicity of low complexity tilings. CoRR, abs/1904.01267, 2019. URL: http://arxiv.org/abs/1904.01267.
-
Douglas Lind and Brian Marcus. Symbolic Dynamics and Coding. Cambridge University Press, 1995.
- Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d'Analyse Mathématique, 53(1):139-186, December 1989. URL: https://doi.org/10.1007/BF02793412.
- Ronnie Pavlov and Michael Schraudner. Entropies realizable by block gluing ℤ^d shifts of finite type. Journal d'Analyse Mathématique, 126(1):113-174, April 2015. URL: https://doi.org/10.1007/s11854-015-0014-4.
- Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones mathematicae, 12(3):177-209, September 1971. URL: https://doi.org/10.1007/BF01418780.
- Hao Wang. Proving theorems by pattern recognition - II. The Bell System Technical Journal, 40(1):1-41, 1961. URL: https://doi.org/10.1002/j.1538-7305.1961.tb03975.x.