Decidability of equivalence for a class of non-deterministic tree transducers
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) no. 5, pp. 447-463.
@article{ITA_1994__28_5_447_0,
     author = {Andr\'e, Yves and Dauchet, Max},
     title = {Decidability of equivalence for a class of non-deterministic tree transducers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {447--463},
     publisher = {EDP-Sciences},
     volume = {28},
     number = {5},
     year = {1994},
     mrnumber = {1296647},
     zbl = {0884.68095},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1994__28_5_447_0/}
}
TY  - JOUR
AU  - André, Yves
AU  - Dauchet, Max
TI  - Decidability of equivalence for a class of non-deterministic tree transducers
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1994
SP  - 447
EP  - 463
VL  - 28
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1994__28_5_447_0/
LA  - en
ID  - ITA_1994__28_5_447_0
ER  - 
%0 Journal Article
%A André, Yves
%A Dauchet, Max
%T Decidability of equivalence for a class of non-deterministic tree transducers
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1994
%P 447-463
%V 28
%N 5
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1994__28_5_447_0/
%G en
%F ITA_1994__28_5_447_0
André, Yves; Dauchet, Max. Decidability of equivalence for a class of non-deterministic tree transducers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) no. 5, pp. 447-463. http://www.numdam.org/item/ITA_1994__28_5_447_0/

1. L. Boasson and J.-M. Autebert, Transductions rationnelles. Applications aux langages algébriques, Masson, Collection ERI, 1988. | MR | Zbl

2. A. Arnold and M. Dauchet, Morphismes et bimorphismes d'arbres, Theoretical Computer Sciences, 1982, 20, pp. 33-93. | MR | Zbl

3. J. Berstel, Transductions and context-free languages, Teubner Verlag Stuttgart, 1979. | MR | Zbl

4. S. Bozapalidis, Alphabetic tree relations, TCS 99. 1992, p. 177-211. | MR | Zbl

5. M. Dauchet and S. Tison, The theory of ground rewrite Systems is decidable, Proceedings of 5th IEEE Symposium on Logic in Computer Sciences, Philadelphia, June 4-7, 1990, pp. 242-248. | MR

6. J. Doner, Tree acceptors and some of their applications, Journal of Computer and System Sciences, 1970, 4, pp. 406-451. | MR | Zbl

7. J. Engelfriet, Bottom-up and top-down tree transformations: a comparison, Mathematical system theory, 1975, 9, pp. 198-231. | MR | Zbl

8. J. Engelfriet, Top-down tree transducers with regular look-ahead, Mathematical System Theory, 1977, 10, pp. 289-303. | MR | Zbl

9. J. Engelfriet, A hierarchy of tree transucers, Proc. 3e colloque sur les Arbres en Algèbre et en Programmation, Université de Lille I, 1978. | MR | Zbl

10. J. Engelfriet, Some open questions and recent results on tree transducers and tree languages, Formal language theory, Academic press, 1980, pp. 241-286.

11. Z. Esik, Decidability results concerning tree transducers I, Acta Cybernetica, 1980, Tome 5, Fasc. 1, pp. 1-20, Szeged. | MR | Zbl

12. C. Frougny and J. Sakarovitch, Relations rationnelles à délai borné. Actes des Journées Montoises, 49-52, Université de Mons-Hainaut, Belgique, 1990, Proceedings of International Colloquium on Words, Languages and Combinatorics, Kyoto, 1990.

13. F. Gecseg and M. Steinby, Tree automata, Akademiai Kiado, Budapest, 1984. | MR | Zbl

14. M. O. Rabin, Decidability of second-order theories and automata on infinite trees, 1969, 141, Trans. Amer. Math. Soc., pp. 1-35. | MR | Zbl

15. W. C. Rounds, Trees, transducers and transformations, Ph. D. Dissertation, Stanford University, 1968. | MR

16. H. Seidl, Equivalence of finite-valued bottom-up finite state tree transducers is decidable, Universität des Saarlandes, Saarbrücken, Germany, Proceeding of CAAP 90, pp. 269-284. | MR | Zbl

17. J. W. Thatcher, Generalized2 sequential machines, Journal of Computer and System Sciences, 1970, 4, pp. 339-367. | Zbl

18. S. Tison, Automates comme outil de décision dans les arbres, Dossier d'habilitation à diriger des recherches, Lille, 1990.

19. Z. Zachar, The solvability of the equivalence problem for deterministic frontier-to-root tree transducers, Acta Cybernetica, 1978, v.4., pp. 167-177. | MR | Zbl