Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 2

available in:   PDF (179 kB) PS (135 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-02-0184


On Quasi-Products of Tree Automata

Ferenc Gécseg (University of Szegeds, Hungary)

Abstract: In this paper we introduce the concept of the quasi-product of tree automata. In a quasi-product the inputs of the component tree automata are operational symbols in which permutation and unification of variables are allowed. It is shown that in sets of tree automata which are homomorphically complete with respect to the quasi-product the essentially unary operations play the basic role among all operations with nonzero ranks. Furthermore, we give a characterization of homomorphically complete sets which is similar to the classical one.

1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.

Keywords: complete sets, products, tree automata

Categories: F.1.1