Decidability of equivalence for a class of non-deterministic tree transducers
André, Yves ; Dauchet, Max
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 447-463 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@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},
     volume = {28},
     year = {1994},
     pages = {447-463},
     mrnumber = {1296647},
     zbl = {0884.68095},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 447-463. http://gdmltest.u-ga.fr/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 969364 | Zbl 0758.68041

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

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

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

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 1099177

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

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

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

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 505844 | Zbl 0386.68070

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 599040 | Zbl 0456.68098

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 735615 | Zbl 0537.68056

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

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

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 1075033 | Zbl 0758.68049

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

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 525042 | Zbl 0401.68058