Decidability of equivalence for a class of non-deterministic tree transducers

Yves André; Max Dauchet

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1994)

  • Volume: 28, Issue: 5, page 447-463
  • ISSN: 0988-3754

How to cite

top

André, Yves, and Dauchet, Max. "Decidability of equivalence for a class of non-deterministic tree transducers." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.5 (1994): 447-463. <http://eudml.org/doc/92490>.

@article{André1994,
author = {André, Yves, Dauchet, Max},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {tree transducer},
language = {eng},
number = {5},
pages = {447-463},
publisher = {EDP-Sciences},
title = {Decidability of equivalence for a class of non-deterministic tree transducers},
url = {http://eudml.org/doc/92490},
volume = {28},
year = {1994},
}

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
PB - EDP-Sciences
VL - 28
IS - 5
SP - 447
EP - 463
LA - eng
KW - tree transducer
UR - http://eudml.org/doc/92490
ER -

References

top
  1. 1. L. BOASSON and J.-M. AUTEBERT, Transductions rationnelles. Applications aux langages algébriques, Masson, Collection ERI, 1988. Zbl0758.68041MR969364
  2. 2. A. ARNOLD and M. DAUCHET, Morphismes et bimorphismes d'arbres, Theoretical Computer Sciences, 1982, 20, pp. 33-93. Zbl0486.68072MR652427
  3. 3. J. BERSTEL, Transductions and context-free languages, Teubner Verlag Stuttgart, 1979. Zbl0424.68040MR549481
  4. 4. S. BOZAPALIDIS, Alphabetic tree relations, TCS 99. 1992, p. 177-211. Zbl0765.68068MR1168459
  5. 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. MR1099177
  6. 6. J. DONER, Tree acceptors and some of their applications, Journal of Computer and System Sciences, 1970, 4, pp. 406-451. Zbl0212.02901MR287977
  7. 7. J. ENGELFRIET, Bottom-up and top-down tree transformations: a comparison, Mathematical system theory, 1975, 9, pp. 198-231. Zbl0335.68061MR398700
  8. 8. J. ENGELFRIET, Top-down tree transducers with regular look-ahead, Mathematical System Theory, 1977, 10, pp. 289-303. Zbl0369.68048MR489019
  9. 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. Zbl0386.68070MR505844
  10. 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. 11. Z. ESIK, Decidability results concerning tree transducers I, Acta Cybernetica, 1980, Tome 5, Fasc. 1, pp. 1-20, Szeged. Zbl0456.68098MR599040
  12. 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. 13. F. GECSEG and M. STEINBY, Tree automata, Akademiai Kiado, Budapest, 1984. Zbl0537.68056MR735615
  14. 14. M. O. RABIN, Decidability of second-order theories and automata on infinite trees, 1969, 141, Trans. Amer. Math. Soc., pp. 1-35. Zbl0221.02031MR246760
  15. 15. W. C. ROUNDS, Trees, transducers and transformations, Ph. D. Dissertation, Stanford University, 1968. MR2617844
  16. 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. Zbl0758.68049MR1075033
  17. 17. J. W. THATCHER, Generalized2 sequential machines, Journal of Computer and System Sciences, 1970, 4, pp. 339-367. Zbl0198.03303
  18. 18. S. TISON, Automates comme outil de décision dans les arbres, Dossier d'habilitation à diriger des recherches, Lille, 1990. 
  19. 19. Z. ZACHAR, The solvability of the equivalence problem for deterministic frontier-to-root tree transducers, Acta Cybernetica, 1978, v.4., pp. 167-177. Zbl0401.68058MR525042

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.