Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 :
Reports (Research report)
Complete list of metadata
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:24 AM
Last modification on : Wednesday, October 26, 2022 - 8:14:13 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