Distinguishability, simulation and universality of Moore

• Autorzy: Jurvanen E. , Lipponen M.
• Języki publikacji: EN

Abstrakty

EN

We extend the notions of distinguishability of states, simulation and universality of string automata to tree automata of Moore type. In particular, we prove that for each finite class of tree automata satisfying certain conditions, there is a unique minimal universal tree automaton. The transfer from strings to rees brings new aspects but also adds difficulties in generalizing classical Moore results.

Słowa kluczowe

EN

tree automata; Moore experiment; distinguishability; simulation; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 79--91
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Jurvanen E.

autor

Lipponen M.

• Department of Mathematics, University of Turku, FIN-20014 Turku, Finland,