Generalized Cayley Graphs and Cellular Automata over them


Pablo Arrighi, LIG. 7 février 2013 10:00 limd 2:00:00
Abstract:

Cellular Automata can be characterized as the translation-invariant continuous functions, where continuity is with respect to a certain distance over the set of configurations. This distance, and its properties, easily extend from grids to Cayley graphs. As a consequence, Cellular Automata also extend from grids to Cayley graphs. Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their equality; to name all vertices relative to a point; the fact that they have a well-defined notion of translation, and that they can be endowed with such a compact metric. But they are very regular. We propose a notion of graph associated to a language, which conserves or generalizes these features. These associated graphs can be arbitrary, although of a bounded degree. We extend Cellular Automata to these Generalized Cayley graphs, so that they define a local dynamics over time-varying graphs.