DECIDABILITY OF EQUIVALENCE FOR A CLASS OF NONDETERMINISTIC TREE-TRANSDUCERS

Authors
ANDRE Y DAUCHET M
Citation
Y. Andre et M. Dauchet, DECIDABILITY OF EQUIVALENCE FOR A CLASS OF NONDETERMINISTIC TREE-TRANSDUCERS, Informatique theorique et applications, 28(5), 1994, pp. 447-463
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
Journal title
Informatique theorique et applications → ACNP
ISSN journal
09883754
Volume
28
Issue
5
Year of publication
1994
Pages
447 - 463
Database
ISI
SICI code
0988-3754(1994)28:5<447:DOEFAC>2.0.ZU;2-N
Abstract
In this paper, we consider non-deterministic tree transducers in the l etter to letter case, that is to say tree transducers for which trees which appear in the rules are reduced to one letter in the right-hand side as in the left one. We establish the decidability of equivalence for linear and non-deleting top-down transducers. These results are va lid in the bottom-up case.