Hyperbolic Recognition by Cellular Automata

Abstract

(eng) Graph automata were first introduced by P. Rosenstiehl. A. Wu and A. Rosenfeld showed later how a graph automaton can study its own structure, by building a system of signals that explore the underlying graph, giving in this way algorithms in linear time allowing to know if the graph is a regular grid. Then, E. Rémila extended this result to other geometrical structures. We show here a very general method that allows to recognize all finite subsets of some Cayley graphs, without using some particular Euclidean information, like orientation, but some more general properties of automatic groups. Depending on the class of graphs we want to recognize, we can finally do different processing on the border of the detected geometrical structure, by using the small cancellations theorem. We study such graphs due to their good properties in network computing.