Register Cellular Automata in the Hyperbolic Plane

• Autorzy: Grigorieff S. , Margenstern M.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider cellular automata on special grids of the hyperbolic plane: the grids are constructed on infinigons, i.e. polygons with infinitely many sides. We show that the truth of arithmetical formulas can be decided in finite time with infinite initial recursive configurations. Next, we define a new kind of cellular automata, endowed with data and more powerful operations which we call register cellular automata. This time, starting from finite configurations, it is possible to decide the truth of arithmetic formulas in linear time with respect to the size of the formula.

Słowa kluczowe

EN

cellular automata; sequential machine theory; parallel processing; pattern recognition system; swarm intelligence; polygons

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 61, nr 1
• Strony: 19--27
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Grigorieff S.

• LIAFA. Universite Paris 7, 2, pl. Jussieu 75251 Paris Cedex 05, France

autor

Margenstern M.

• LITA, EA 3097, Universite de Metz. lie du Saulcy 57045 Metz Cedex, France

Bibliografia

• [1] L. Blum, F. Clicker, M. Shub, S. Smale, Complexity nd Real Computations, Springer, Berlin, 199K.
• [2] Burgin M., Universal limit Turing machines. Notices ofthe Russian Academy of Sciences. 325, N°4, (1992), 654-658.
• [3] H. S. M. Coxeter, World-structure and non-Euclidean honeycombs. Proceedings of the Royal Mathematical Society of London. 201. 417-437. (1950)
• [4] Hogarth, M. L., Non-Turing Computers and Non-Turing Computability, in PSA 1994. D. Hull, M. Forbes and R.M. Burian (eds.), (1994), 126-138.
• [5] Margenstem M., New Tools for Cellular Automata of the Hyperbolic Plane, Journal of Universal Computer Science 6 No 12, 1226-1252, (2000)
• [6] Margenstem M., Cellular automata in the hyperbolic plane. A survey, Romanian Journal of Information Science and Technology, 5, N°l-2, (2000), 155-179, (invited paper).
• [7] Margenstem M., Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces, a survey. Lecture Notes of Computer Sciences 2731. (2003), 48-72, Proceedings of DMTCS'2003, Dijon, July, 7-12, 2003, invited talk.
• [8] Margenstem M., On the Infinigons of the Hyperbolic Plane, A Combinatorial Approach, Fundamenta Informaticae, 56 N°3, (2003), 255-272.
• [9| Margenstem M., Morita K., NP problems are tractable in the space of cellular automata in the hyperbolic plane. Technical report. Publications of the I.U.T. of Metz, 38p. 1998.
• [10] Margenstem M., Morita K., NP problems are tractable in the space of cellular automata in the hyperbolic plane. Theoretical Computer Science, 259. 99-128, (2001)
• [11] Matiyasevich Yu.V., Hilbert's Tenth Problem. Nauka Publishers, Fizmatlit, (1993) (Russian; English translation: MIT Press, 1993).
• [12] Putnam H., Trial and Error Predicates and the Solution to a Problem of Mostowski, Joumal of Symbolic Logic, 30, N.l. (1965). 49-57.
• [13] Rozenfel'd, B. A., Neevklidovy prostranstva, Nauka. Moscow, (1969), 548pp. (Noneuclidean spaces, in Russian).