Automates à galets : un état de l'art.

Marianne Delorme (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

The purpose of this paper is to give an overview on pebble automata, which can be encountered in different domains, as figures (families) recognition, complexity theory and labyrinths theory . It gives definitions, examples and some basic theorems with their proofs.

Ce rapport est un état de l'art sur les automates à galets que l'on rencontre dans divers domaines comme celui de la reconnaissance de (familles de) figures, théorie de la Complexité, mais aussi théorie des labyrinthes.

Mots clés: Automata; Automates; Graphoids; Labyrinths; Pebbles

Mots clés: Galets; Graphoides; Labyrinthes

Domaines: Informatique [cs]

Marianne Delorme. Automates à galets : un état de l'art.. [Research Report] LIP RR-1997-23, Laboratoire de l'informatique du parallélisme. 1997, 2+52p. ⟨hal-02101923⟩