Distinguishability, Simulation and Universality of Moore Tree Automata

Article type: Research Article

Authors: Jurvanen, Eija | Lipponen, Marjo

Affiliations: Turku Centre for Computer Science, and Department of Mathematics, University of Turku Lemminkäisenkatu 14 A FIN-20520 Turku, Finland email: {jurvanen,marlip}@utu.fi

Note: [] Address for correspondence: Department of Mathematics, University of Turku, FIN-20014 Finland.

Abstract: 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 trees brings new aspects but also adds difficulties in generalizing classical Moore results.

Keywords: tree automata, Moore experiments, distinguishability, simulation, universality

DOI: 10.3233/FI-1999-381207

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 79-91, 1999