Skip to Main content Skip to Navigation

Hyperbolic Recognition by Cellular Automata

Abstract : 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.
Document type :
Complete list of metadatas
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:24 AM
Last modification on : Wednesday, November 20, 2019 - 2:52:56 AM


Files produced by the author(s)


  • HAL Id : hal-02101943, version 1



Christophe Papazian, Eric Rémila. Hyperbolic Recognition by Cellular Automata. [Research Report] LIP RR-2002-03, Laboratoire de l'informatique du parallélisme. 2002, 2+14p. ⟨hal-02101943⟩



Record views


Files downloads