Pebble Automata. Figures Families Recognition and Universality

Issue title: Cellular Automata

Article type: Research Article

Authors: Delorme, Marianne | Mazoyer, Jacques

Affiliations: LIP, ENS Lyon, 46 Allée d'Italie, 69 364 Lyon Cedex 07, France

Abstract: In this paper, we consider the pebble automata introduced by Blum and Hewitt, but now moving through the unbounded plane Z^2. We are interested in their ability to recognize families of dotted figures. Contrary to the bounded case studied by Blum and Hewitt, the hierarchy collapses: there are families recognized with 0, 1, 2 and 3 pebbles, but each family recognized with more than three pebbles is recognized with exactly 3 ones. This result is connected to the existence of an intrinsically universal} 3-pebble-automaton. We formally define the underlying universality notion, and prove that there exists some 3-pebble automaton intrinsically universal, but no such automaton with only 2 pebbles.

Keywords: figure recognition, pebble automata, universality

Journal: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 81-132, 2002