Hyperbolic Recognition by Cellular Automata
Résumé
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.
Les graphes d'automates ont été introduites par P. Rosensthiel. A. Wu et A. Rosenfeld ont ensuite montré comment un graphe d'automates peut étudier la propre structure, en construisant un système de signaux qui explorent le graphe sous jacent., donnant ainsi un algorithme en temps linéaire permettant à un graphe d'automates de savoir si son graphe est un rectangle, puis E. Rémila a étendu cette reconnaissance à d'autres structure géométriques.
Nous proposons ici une méthode très générale qui permet de reconnaître les classes des sous-graphes finis de certains graphes de cayley, sans utiliser des propriétés euclidiennes, comme la notion d'orientation, mais des propriétés très générales, comme celles des groupes automatiques?. Selon la classe de graphe que l'on souhaite reconnaître, on peut alors effectuer des traitements différents de reconnaissance sur les bords de la structure géométrique détectée, en utilisant le théorème des petites simplifications
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|