Skip to main content
SpringerLink
Log in

Cellular Automata in Hyperbolic Spaces

  • Living reference work entry
  • First Online:
Encyclopedia of Complexity and Systems Science

Definition of the Subject and Its Importance

Cellular automata in hyperbolic spaces, in short hyperbolic cellular automata (abbreviated HCA), consists in the implementation of cellular automata in the environment of a regular tiling of a hyperbolic space.

The first implementation of such an object appeared in a paper by the present author and Kenichi Morita in 1999 (see Margenstern and Morita 1999). In this first paper, a first solution to the location problem in this context was given. The paper also focused on one advantage of this implementation: it allows to solve NP problems in polynomial time. In 2000, a second paper appeared, by the present author, where a decisive solution of the location problem was given.

The study of HCAs is a new domain in computer science, at the border with mathematics and physics. They involve hyperbolic geometry as well as elementary arithmetic and algebra with the connections of polynomials with matrices and also some theory of fields. They also...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Abbreviations

Dodecagrid:

The tiling {5, 3, 4}. This tessellation lives in the hyperbolic 3D space. Its basic polyhedron is the dodecahedron constructed on regular rectangular pentagons.

Fibonacci sequence:

Sequence of natural integers, denoted by f n and defined by the recurrent equation \( {f}_{n+2}={f}_{n+1}+{f}_n, \) for all n ∈ ℕ and by the initial values f 0 = f 1 = 1.

Heptagrid:

The tiling {7, 3}, necessarily in the hyperbolic plane. Seven sides and three tiles around a vertex. It is called ternary heptagrid in several papers by the author and its coauthors also in Margenstern (2007c, 2008b).

Hyperbolic geometry:

Geometry, discovered by Nikolaj Lobachevsky and Jànos Bolyai, independently of each other and around 1830. This geometry satisfies the axioms of Euclidean geometry, the axiom of parallels being excepted and replaced by the following one: through a point out of a line, there are exactly two parallels to the line. In this geometry, there are also lines which never meet: they are called non-secant. They are characterized by the existence, for any couple of such lines, of a unique common perpendicular. Also, in this geometry, the sum of the interior angles of a triangle is always less than π. The difference to π defines the area of the triangle. In hyperbolic geometry, distances are absolute: there is no notion of similarity. See also Poincaré’s disk.

Invariant group of a tiling:

Group of transformations which defines a bijection on the set of tiles. Usually, in a geometrical space, they are required to belong to the group of isometries of the space.

Pentagrid:

The tiling {5, 4}, necessarily in the hyperbolic plane. Five sides and four tiles around a vertex. The angles are right angles.

Poincaré’s disk:

Model of the hyperbolic plane inside the Euclidean plane. The points are those which are interior to a fixed disk D. The lines are the trace in D of diameters or circles which are orthogonal to the border of D. The model was first found by Beltrami and then by Poincaré who also devised the half-plane model also called after his name. The half-plane model is a conformal image of the disk model.

Tessellation:

Particular case of a finitely generated tiling. It is defined by a polygon and by its reflections in its sides and, recursively, of the images in their sides.

Tiling:

Partition of a geometrical space; the closure of the elements of the partition is called the tiles. An important case is constituted by finitely generated tilings: there is a finite set of tiles G such that any tile is a copy of an element of G.

Tiling {p, q}:

Tessellation based on the regular polygon with p sides and with vertex angle \( \frac{2\uppi}{q}. \)

Bibliography

  • Berger R (1966) The undecidability of the domino problem. Mem Am Math Soc 66:1–72

    MathSciNet  MATH  Google Scholar 

  • Chelghoum K, Margenstern M, Martin B, Pecci I (2004) Cellular automata in the hyperbolic plane: proposal for a new environment. Lect Notes Comput Sci 3305:678–687, proceedings of ACRI’2004, Amsterdam, October, 25–27, 2004

    Article  MATH  Google Scholar 

  • Cook M (2004) Universality in elementary cellular automata. Complex Syst 15(1):1–40

    MathSciNet  MATH  Google Scholar 

  • Fraenkel AS (1985) Systems of numerations. Am Math Mon 92:105–114

    Article  MathSciNet  Google Scholar 

  • Gromov M (1981) Groups of polynomial growth and expanding maps. Publ Math l’IHES 53:53–73

    Article  MathSciNet  MATH  Google Scholar 

  • Hedlund G (1969) Endomorphisms and automorphisms of shift dynamical systems. Math Syst Theory 3:320–375

    Article  MathSciNet  MATH  Google Scholar 

  • Herrmann F, Margenstern M (2003) A universal cellular automaton in the hyperbolic plane. Theor Comp Sci 296:327–364

    Article  MathSciNet  MATH  Google Scholar 

  • Iwamoto Ch, Margenstern M (2003) A survey on the complexity classes in hyperbolic cellular automata. Proceedings of SCI’2003, V, pp 31–35

    Google Scholar 

  • Iwamoto Ch, Margenstern M, Morita K, Worsch Th (2002) Polynomial-time cellular automata in the hyperbolic plane accept exactly the PSPACE languages. SCI’2002. Orlando, pp 411–416

    Google Scholar 

  • Kari J (2007) The tiling problem revisited. Lect Notes Comput Sci 4664:72–79

    Article  MATH  Google Scholar 

  • Lindgren K, Nordahl MG (1990) Universal computations in simple one-dimensional cellular automata. Complex Syst 4:299–318

    MathSciNet  MATH  Google Scholar 

  • Margenstern M (2000) New tools for cellular automata in the hyperbolic plane. J Univ Comp Sci 6(12):1226–1252

    MathSciNet  MATH  Google Scholar 

  • Margenstern M (2002a) A contribution of computer science to the combinatorial approach to hyperbolic geometry, SCI’2002, 14–19 July 2002. Orlando

    Google Scholar 

  • Margenstern M (2002b) Revisiting Poincaré’s theorem with the splitting method, talk at Bolyai’200, International Conference on Geometry and Topology, Cluj-Napoca, Romania, 1–3 October 2002

    Google Scholar 

  • Margenstern M (2003) Implementing cellular automata on the triangular grids of the hyperbolic plane for new simulation tools, ASTC’2003. Orlando, 29 Mar- 4 Apr

    Google Scholar 

  • Margenstern M (2004) The tiling of the hyperbolic 4D space by the 120-cell is combinatoric. J Univ Comp Sci 10(9):1212–1238

    MathSciNet  Google Scholar 

  • Margenstern M (2006a) A new way to implement cellular automata on the penta- and heptagrids. J Cell Autom 1(1):1–24

    MathSciNet  MATH  Google Scholar 

  • Margenstern M (2006b) A universal cellular automaton with five states in the 3D hyperbolic space. J Cell Autom 1(4):317–351

    Google Scholar 

  • Margenstern M (2007a) On the communication between cells of a cellular automaton on the penta- and heptagrids of the hyperbolic plane. J Cell Autom (to appear)

    Google Scholar 

  • Margenstern M (2007b) About the domino problem in the hyperbolic plane, a new solution. arXiv:cs/0701096, (Jan 2007), p 60

    Google Scholar 

  • Margenstern M (2007c) Cellular automata in hyperbolic spaces, theory, vol 1. Old City Publishing, Philadelphia, 422p

    MATH  Google Scholar 

  • Margenstern M (2008a) A uniform and intrinsic proof that there are universal cellular automata in hyperbolic spaces. J Cell Autom 3(2):157–180

    MathSciNet  MATH  Google Scholar 

  • Margenstern M (2008b) Cellular automata in hyperbolic spaces, volume 2, implementation and computation. Old City Publishing, Philadelphia, 360p

    MATH  Google Scholar 

  • Margenstern M (2008c) The domino problem of the hyperbolic plane is undecidable. Theor Comp Sci 407:29–84

    Article  MathSciNet  MATH  Google Scholar 

  • Margenstern M (2008d) On a characterization of cellular automata in tilings of the hyperbolic plane. Int J Found Comp Sci 19(5):1235–1257

    Article  MathSciNet  MATH  Google Scholar 

  • Margenstern M (2008e) The finite tiling problem is undecidable in the hyperbolic plane. Int J Found Comp Sci 19(4):971–982

    Article  MathSciNet  MATH  Google Scholar 

  • Margenstern M (2009a) The periodic domino problem is undecidable in the hyperbolic plane. Lect Notes Comput Sci 5797:154–165

    Article  ADS  MATH  Google Scholar 

  • Margenstern M (2009b) The injectivity of the global function of a cellular automaton in the hyperbolic plane is undecidable. Fundam Inform 94(1):63–99

    MathSciNet  MATH  Google Scholar 

  • Margenstern M (2009c) About the garden of Eden theorems for cellular automata in the hyperbolic plane. Electron Notes Theor Comp Sci 252:93–102

    Article  MathSciNet  Google Scholar 

  • Margenstern M (2010a) A weakly universal cellular automaton in the hyperbolic 3D space with three states. Discrete Mathematics and Theoretical Computer Science. Proceedings of AUTOMATA’2010, pp 91–110

    Google Scholar 

  • Margenstern M (2010b) Towards the frontier between decidability and undecidability for hyperbolic cellular automata. Lect Notes Comput Sci 6227:120–132

    Article  ADS  MATH  Google Scholar 

  • Margenstern M (2010c) An upper bound on the number of states for a strongly universal hyperbolic cellular automaton on the pentagrid, JAC’2010, 15–17 Dec 2010. Turku, Finland, Proceedings, Turku Center for Computer Science 2010. ISBN 978-952-12-2503-1, 168-179

    Google Scholar 

  • Margenstern M (2011a) A new weakly universal cellular automaton in the 3D hyperbolic space with two states. Lect Notes Comput Sci 6945:205–2017

    Article  MATH  Google Scholar 

  • Margenstern M (2011b) A universal cellular automaton on the heptagrid of the hyperbolic plane with four states. Theor Comp Sci 412:33–56

    Article  MathSciNet  MATH  Google Scholar 

  • Margenstern M (2012) A protocol for a message system for the tiles of the heptagrid, in the hyperbolic plane. Int J Satell Commun Policy Manag 1(2–3):206–219

    Article  Google Scholar 

  • Margenstern M (2013a) Small universal cellular in hyperbolic spaces, a collection of jewels. Emergence, Complexity and Computation, Springer, p 320

    Google Scholar 

  • Margenstern M (2013b) About strongly universal cellular automata. arXiv. 1304.6316v1 [cs.DM], pp 28

    Google Scholar 

  • Margenstern M, Morita K (1999) A polynomial solution for 3-SAT in the space of cellular automata in the hyperbolic plane. J Univ Comput Syst 5:563–573

    MathSciNet  MATH  Google Scholar 

  • Margenstern M, Morita K (2001) NP problems are tractable in the space of cellular automata in the hyperbolic plane. Theor Comp Sci 259:99–128

    Article  MathSciNet  MATH  Google Scholar 

  • Margenstern M, Skordev G (2003a) The tilings {p, q} of the hyperbolic plane are combinatoric, SCI’2003, V, pp 42–46

    Google Scholar 

  • Margenstern M, Skordev M (2003b) Tools for devising cellular automata in the hyperbolic 3D space. Fundam Inform 58(2):369–398

    MathSciNet  MATH  Google Scholar 

  • Margenstern M, Song Y (2008) A universal cellular automaton on the ternary heptagrid. Electron Notes Theor Comp Sci 223:167–185

    Article  MATH  Google Scholar 

  • Margenstern M, Song Y (2009) A new universal cellular automaton on the pentagrid. Parallel Process Lett 19(2):227–246

    Article  MathSciNet  Google Scholar 

  • Morgenstein D, Kreinovich V (1995) Which algorithms are feasible and which are not depends on the geometry of space-time. Geombinatorics 4(3):80–97

    MATH  Google Scholar 

  • Martin B (2005) VirHKey: a virtual hyperbolic keyboard with gesture interaction and visual feedback for mobile devices, MobileHCI’05, Sept. Salzburg

    Google Scholar 

  • Robinson RM (1971) Undecidability and nonperiodicity for tilings of the plane. Invent Math 12:177–209

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Robinson RM (1978) Undecidable tiling problems in the hyperbolic plane. Invent Math 44:259–264

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Róka Z (1994) One-way cellular automata on Cayley graphs. Theor Comp Sci 132:259–290

    Article  MathSciNet  MATH  Google Scholar 

  • Stewart I (1994) A subway named turing, mathematical recreations in scientific American. pp 90–92

    Google Scholar 

  • Wolfram S (2002) A new kind of science. Wolfram Media

    Google Scholar 

Download references

Acknowledgment

The author again thanks Andrew Adamatzky for giving him the task to write the first issue of this entry. He is also much in debt to Andrew Spencer for asking him this new version.

Author information

Authors and Affiliations

  1. Université de Lorraine, LITA, EA 3097, Campus du Saulcy, 57045, Cédex, Metz, France

    Maurice Margenstern

Authors
  1. Maurice Margenstern
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maurice Margenstern .

Editor information

Editors and Affiliations

  1. Ramtech Ltd., Larkspur, California, USA

    Robert A. Meyers

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer Science+Business Media New York

About this entry

Cite this entry

Margenstern, M. (2015). Cellular Automata in Hyperbolic Spaces. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27737-5_53-5

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27737-5_53-5

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Online ISBN: 978-3-642-27737-5

  • eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics

Publish with us

Policies and ethics

Search

Navigation