An Algorithmic Approach to Tilings of Hyperbolic Spaces: Universality Results

• Autorzy: Margenstern M.

Identyfikatory

DOI

10.3233/FI-2015-1202

• Języki publikacji: EN

Abstrakty

EN

In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states.

Słowa kluczowe

EN

hyperbolic spaces; tilings; cellular automata; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 113--125
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Margenstern M.

• Universit´e de Lorraine, LITA EA 3097, Campus du Saulcy 57045 METZ Cedex 1, France

Bibliografia

• [1] R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 66, (1966), 1-72.
• [2] K. Chelghoum, M. Margenstern, B. Martin, I. Pecci, Tools for implementing cellular automata in grid {7, 3} of the hyperbolic plane, DMCS’2004, (2004).
• [3] M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), (2004), 1-40.
• [4] G. Hedlund, Endomorphisms and automorphisms of shift dynamical systems, Math. Systems Theory, 3, (1969), 320-375.
• [5] F. Herrmann, M. Margenstern, A universal cellular automaton in the hyperbolic plane, Theoretical Computer Science, (2003), 296, 327-364.
• [6] K. Lindgren, M.G. Nordahl, Universal Computations in Simple One-Dimensional Cellular Automata, Complex Systems, 4, (1990), 299-318.
• [7] M. Margenstern, New Tools for Cellular Automata of the Hyperbolic Plane, Journal of Universal Computer Science, 6(12), (2000), 1226–1252.
• [8] M. Margenstern, A contribution of computer science to the combinatorial approach to hyperbolic geometry, SCI’2002, (2002).
• [9] M. Margenstern, Revisiting Poincar´e’s theorem with the splitting method, Bolyai 200, International Conference on Hyperbolic Geometry, Cluj-Napoca, Romania, October, 1-4, (2002).
• [10] M. Margenstern, Implementing Cellular Automata on the Triangular Grids of the Hyperbolic Plane for New Simulation Tools, ASTC’2003, (2003).
• [11] M. Margenstern, The tiling of the hyperbolic 4D space by the 120-cell is combinatoric, Journal of Universal Computer Science, 10(9), (2004), 1212-1238.
• [12] M.Margenstern, A new way to implement cellular automata on the penta- and heptagrids, Journal of Cellular Automata 1(1), (2006), 1-24.
• [13] M. Margenstern, A universal cellular automaton with five states in the 3D hyperbolic space, Journal of Cellular Automata 1(4), (2006), 315-351.
• [14] M. Margenstern, About the domino problem in the hyperbolic plane, a new solution, arXiv:0701096[cs,CG], 60p.
• [15] M. Margenstern, Cellular Automata in Hyperbolic Spaces, vol. 1, Theory, Old City Publishing, Philadelphia, (2007), 422p.
• [16] M. Margenstern, The Domino Problem of the Hyperbolic Plane is Undecidable, Bulletin of the EATCS, 93, October, (2007), 220-237.
• [17] M.Margenstern, The domino problem of the hyperbolic plane is undecidable, Theoretical Computer Science, 407, (2008), 29-84.
• [18] M. Margenstern, The Finite Tiling Problem Is Undecidable in the Hyperbolic Plane, International Journal of Foundations of Computer Science, 19(4), (2008), 971-982.
• [19] M. Margenstern, The periodic domino problem is undecidable in the hyperbolic plane, Lecture Notes in Computer Sciences, 5797, (2009), 154-165.
• [20] M. Margenstern, A universal cellular automaton on the heptagrid of the hyperbolic plane with four states, Theoretical Computer Science, (2010), to appear
• [21] M. Margenstern, A weakly universal cellular automaton in the hyperbolic 3D space with three states, arXiv:1002.4290v1[cs,DS], 54p.
• [22] M. Margenstern, A weakly universal cellular automaton in the hyperbolic 3D space with two states, arXiv:1005.4826v1[cs,FL], 38p.
• [23] M. Margenstern, Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels, Springer Verlag, (2013), 331p.
• [24] M. Margenstern, About Strongly Universal Cellular Automata, Electronic Proceedings in Theoretical Computer Science, 128, (2013), Proceedings of MCU’2013, 93-125.
• [25] M. Margenstern, A weakly universal cellular automaton in the pentagrid with five states, arXiv:1403.2373[cs,DM], 23p.
• [26] M. Margenstern, G. Skordev, Fibonacci Type Coding for the Regular Rectangular Tilings of the Hyperbolic Plane, Journal of Universal Computer Science, 9(5), (2003), 398-422.
• [27] M. Margenstern, G. Skordev, Tools for devising cellular automata in the hyperbolic 3D space, Fundamenta Informaticae, 58(2), (2003), 369-398.
• [28] M. Margenstern, Y. Song, A universal cellular automaton on the ternary heptagrid, Electronic Notes in Theoretical Computer Science, 223, (2008), 167-185.
• [29] M. Margenstern, Y. Song, A new universal cellular automaton on the pentagrid, Parallel Processing Letters, 19(2), (2009), 227-246.
• [30] R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12, (1971), 177-209.
• [31] R.M. Robinson, Undecidable tiling problems in the hyperbolic plane. InventionesMathematicae, 44, (1978), 259-264.
• [32] I. Stewart, A Subway Named Turing, Mathematical Recreations in Scientific American, (1994), 90-92.