Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2002

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Pebble Automata. Figures Families Recognition and Universality

Delorme M., Mazoyer J.

Fundamenta Informaticae

2002

Vol. 52, nr 1-3

81-132

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.