摘要: We state a definition of the simulation graph automata, which are machines built by putting copies same finite-state automaton at vertices regular graph, reading states neighbors. first present notion and link it to intrinsic properties. Afterwards, we some results between such comparing them cellular automata on Cayley graphs. The graphs considered here planar, with elementary cycles length, form tilings hyperbolic plane. conclude possible speed hierarchy.
参考文章(9)
Thomas Chaboud, Pavages et graphes de Cayley planaires Lyon, École normale supérieure (sciences). ,(1995)
Zsuzsanna Roka, Automates cellulaires sur graphes de Cayley Lyon 1. ,(1994)
Angela Yuen Wu, Cellular Graph Automata international workshop on graph grammars and their application to computer science. pp. 464- 475 ,(1978) , 10.1007/BFB0025742
Paul E. Schupp, Roger C. Lyndon, Combinatorial Group Theory ,(1977)
Bruno Martin, A geometrical hierarchy on graphs via cellular automata Fundamenta Informaticae. ,vol. 52, pp. 157- 181 ,(2002)
Max Garzon, Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks ,(2012)
THOMAS CHABOUD, CLAIRE KENYON, PLANAR CAYLEY GRAPHS WITH REGULAR DUAL International Journal of Algebra and Computation. ,vol. 06, pp. 553- 561 ,(1996) , 10.1142/S0218196796000301
Angela Wu, Azriel Rosenfeld, Cellular graph automata. I. basic concepts, graph property measurement, closure properties* Information & Computation. ,vol. 42, pp. 305- 329 ,(1979) , 10.1016/S0019-9958(79)90288-2
W O J Moser, Harold Scott Macdonald Coxeter, Generators and relations for discrete groups ,(1957)