×

On \(\alpha _ i\)-product of tree automata. (English) Zbl 0633.68048

The \(\alpha_ i\)-products of finite automata were defined by the first author [Lect. Notes Comput. Sci. 14, 351-363 (1974; Zbl 0287.94040)] as compositions in which feedback loops are of length i at most. This paper extends the second author’s work on isomorphic representations by \(\alpha_ i\)-products [Acta Cybern. 3, 301-307 (1977; Zbl 0401.68034)] to tree automata. A class of tree automata is said to be isomorphically complete with respect to the \(\alpha_ i\)-product if every tree automaton can be isomorphically embedded into an \(\alpha_ i\)-product of automata from this class.
The authors give criteria for isomorphic completeness and show then that there are no minimal isomorphically complete classes with respect to the \(\alpha_ i\)-products. They also prove that \(\alpha_ i\)-products form a properly ascending hierarchy for increasing values of \(i=0, 1, 2,... \). Finally, it is shown to be decidable whether or not a given tree automaton can be isomorphically embedded into an \(\alpha_ i\)-product of automata from a given finite set.
Reviewer: M.Steinby

MSC:

68Q70 Algebraic theory of languages and automata
08A99 Algebraic structures