Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pebble automata

Sortuj według:

Ogranicz wyniki do:

A Note on Two-pebble Automata Over Infinite Alphabets

Kaminski M., Tan T.

Fundamenta Informaticae

2010

Vol. 98, nr 4

379-390

It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.

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.