ON THE EQUIVALENCE PROBLEM FOR LETTER-TO-LETTER TOP-DOWN TREE-TRANSDUCERS

Letter to letter top-down tree transducers are investigated in this pa per. Informally, trees which appear in the rules of such transducers a re reduced to one letter in the right-hand side as in the left one. Wi th an encoding of the tree transformations induced by such transducers into recognizable forests, we recently established the decidability o f equivalence for linear top-down transducers. Here, in order to captu re the non-linearity of top-down transducers, we introduce new classes of tree automata with equivalence constraints between direct subterms for which equivalence is decidable. We then show that the equivalence problem for non-linear top-down transducers can be reduced to the equ ivalence problem of automata with equivalence constraints. (C) 1998-El sevier Science B.V. All rights reserved.