Simulations Between Cellular Automata on Trees Extended by Horizontal Edges

• Autorzy: Worsch T.
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider cellular automata where the graph defined by the neighbourhood relations between the cells is a tree ``with additional edges''. This includes hyperbolic CA defined by regular tessellations of the two-dimensional hyperbolic plane. It is shown that all X-tree CA and all hyperbolic CA can C-simulate each other with constant slowdown, independent of the ``branching factors'' of the underlying trees.

Słowa kluczowe

EN

cellular automata; extended tree; X-tree; hyperbolic CA

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 241--260
• Opis fizyczny: Bibliogr. 8 poz., wykr.

Twórcy

autor

Worsch T.

• Fakultät für Informatik, Universität Karlsruhe, Germany,

Bibliografia

• [1] Achilles, A.-C., Kutrib, М., Worsch, Т.: On relations between arrays of processing elements of different dimensionality, Parcella '96 (Proceedings of the VII. International Workshop on Parallel Processing by Cellular Automata and Arrays held in Berlin, September 16-20, 1996) (R. Vollmar, W. Erhard, V. Jossifov, Eds.), number 96 in Mathematical research. Akademie Verlag, Berlin, 1996.
• [2] Fachini, E., Gruska, J., Schettini, A. M., Sangiorgi, D.: Simulation of systolic tree automata on trellis automata, International Journal of Foundations of Computer Science, 1(2), 1990, 87-110.
• [3] Fachini, E., Napoli, M.: С-tree systolic automata, Theoretical Computer Science, 56, 1988, 155-186.
• [4] Iwamoto, C., Margenstern, M., Morita, K., Worsch, Т.: Polynomial-Time Cellular Automata in the Hyperbolic Plane Accept Exactly the PSPACE Languages, Proceedings SCI 2002/ISAS 2002, vol. V (N. Callaos, T. Leng, В. Sanchez, Eds.), International Institute of Informatics and Systemics (IUS), International Institute of Informatics and Systemics (IIIS), Orlando, July 2002, ISBN 980-07-8150-1.
• [5] Margenstern, M., Skordev, G.: Fibonacci Type Coding for the Regular Rectangular Tilings of the Hyperbolic Plane, Journal of Universal Computer Science, 9(5), 2003, 398-422
• [6] Mycielski, J., Niwiński, D.: Cellular automata on trees, a model for parallel computation. Fundamenta Informaticae, XV, 1991, 139-144.
• [7] Rosenstiehl, P., Fiksel, J. R., Holliger, A.: Intelligent Graphs: Networks of Finite Automata Capable of Solving Graph Problems, in: Graph Theory and Computing (R. C. Read, Ed.), Academic Press, New York, 1972, 219-265.
• [8] Wu, A., Rosenfeld, A.: Cellular Graph Automata. I. Basic Concepts, Graph Property Measurement, Closure Properties, Information and Control, 42, 1979, 305-329.