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
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101943
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:24 AM
Last modification on : Friday, May 17, 2019 - 1:39:21 AM

File

RR2002-03.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101943, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

2

Files downloads

8