Pebble Automata. Figures Families Recognition and Universality

• Autorzy: Delorme M. , Mazoyer J.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider the pebble automata introduced by Blum and Hewitt, but now moving through the unbounded plane Z2. 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.

Słowa kluczowe

EN

figure recognition; pebble automata; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 52, nr 1-3
• Strony: 81--132
• Opis fizyczny: wykr., bibliogr. 10 poz.

Twórcy

autor

Delorme M.

autor

Mazoyer J.

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