A Geometrical Hierarchy on Graphs via Cellular Automata


B. Martin
Fundamenta Informaticae, 52(1-3):157-179,2002.
 
Back to my home page ...
Back to my publication page ...
 
  • Historically, cellular automata were defined on the lattices $\IZ^n$, but the definition can be extended to bounded degree graphs. Given a notion of simulation between cellular automata defined on different structures (namely graphs of automata), we can deduce an order on graphs. In this paper, we link this order to graph properties and explicit the order for most of the common graphs.

    •  
  • Keywords: cellular automaton, graph of automata, simulation, Cayley graphs, graph growth, hyperbolic space, hierarchy.

    •  
    Download (gzipped postscript)
     
    @Article{marfuin02,
             author = {B. Martin},
             title = {Simulations between cellular automata on {C}ayley graphs},
             journal = {Fondamenta Informaticae},
             volume = {52}
             number = {1-3}
             pages = {157-179}
             year = {2002}
    }