Search

In this paper, we study the contribution of the theory of grossone to the study of infinite Fibonacci words, combining this tool with the help of a particular tiling of the hyperbolic plane: the tiling { 7 , 3 } , called the heptagrid. With the help of the numeral system based on grossone, we obtain a richer family of infinite Fibonacci words compared with the traditional approach. [ABSTRACT FROM AUTHOR]

This paper is the second part of our survey of results on universality for cellular automata in the hyperbolic plane and in the hyperbolic 3D-space. Here we remind the notion of universality and its variants. We also remind the railway model on which many of our results are based for universal cellular autmata in the hyperbolic plane and in the hyperbolic 3D space. We conclude this section with a application to the pentagrid, the heptagrid, the dodecagrid and the tessellation {11, 3} of the hyperbolic plane. [ABSTRACT FROM AUTHOR]

This paper introduces a communication system for the tiles of the heptagrid, a tiling of the hyperbolic plane. The paper focuses on a short account of an experiment obtained by running a simulation programme.

This paper is a contribution to the general tiling problem for the hyperbolic plane. It is an intermediary result between the result obtained by R. Robinson [Invent. Math.44(1978) 259–264] and the conjecture that the problem is undecidable.

In this paper, we define cellular automata on a grid of the hyperbolic plane that is based on the tessellation obtained from the regular pentagon with right angles. Owing to the properties of that grid, we show that 3-SAT can be solved in polynomial time in that peculiar setting; then we extend that result for any NP problem. On this ground, several directions are indicated.

We define a kind of cellular automaton called a hexagonal partitioned cellular automaton (HPCA), and study logical universality of a reversible HPCA. We give a specific 64-state reversible HPCA H1, and show that a Fredkin gate can be embedded in this cellular space. Since a Fredkin gate is known to be a universal logic element, logical universality of H1is concluded. Although the number of states of H1is greater than those of the previous models of reversible CAs having universality, the size of the configuration realizing a Fredkin gate is greatly reduced, and its local transition function is still simple. Comparison with the previous models, and open problems related to these model are also discussed.

We give an application of iterated pushdown automata to contour words of balls and two other domains in infinitely many tilings of the hyperbolic plane. We also give a similar application for the tiling {5,3,4} of the hyperbolic 3D space and for the tiling {5,3,3,4} of the hyperbolic 4D space as well.