No Access

Compositions of Weighted Extended Tree Transducers — The Unambiguous Case

Andreas Maletti

Universität Leipzig, Faculty of Mathematics and Computer Science, PO Box 100920, 04009 Leipzig, Germany

E-mail Address: andreas.maletti@uni-leipzig.de

https://doi.org/10.1142/S0129054123480064Cited by:0 (Source: Crossref)

This article is part of the issue:

Special Issue: Articles Dedicated to the Memory of Magnus Steinby
Guest Editors: Zoltán Fülöp (University of Szeged, Hungary), George Rahonis (University of Thessalonikim Greece) and Kai Salomaa (Queen’s University, Canada)

Abstract

Generalizations of another two open conjectures, Conjectures 13 and 14, of [Lagoutte, Maletti: Survey — Weighted extended top-down tree transducers — Part III: Composition. Proc. AFCS, LNCS 7020, p. 272–308, Springer 2011] are verified. It is proved that the composition of an unambiguous weighted extended tree transducer $M$ with a nondeleting weighted top-down tree transducer $N$ can be computed by a single weighted extended tree transducer. Extending the recent confirmation of Conjecture 11 it is also proved that the composition succeeds for any weighted top-down tree transducer $N$ (even if it is not nondeleting) if the unambiguous weighted extended tree transducer $M$ is constant.

Communicated by Zoltán Fülöp

Contribution dedicated to Magnus Steinby

Keywords:

Remember to check out the Most Cited Articles!
Check out these Handbooks in Computer Science

References

1. C. Allauzen, M. Riley, J. Schalkwyk, W. Skut and M. Mohri, OpenFst — A general and efficient weighted finite-state transducer library, Proc. 12th Int.Conf.Implementation and Application of Automata, eds. J. Holub and J. Žďárek, Lecture Notes in Computer Science 4783 (Springer, 2007), pp. 11–23. Google Scholar
2. A. Arnold and M. Dauchet, Morphismes et bimorphismes d’arbres, Theoretical Computer Science 20(4) (1982) 33–93. Crossref, Web of Science, Google Scholar
3. M. Blattmann and A. Maletti, Compositions with constant weighted extended tree transducers, International Journal on Foundations of Computer Science (2023), in press. Link, Google Scholar
4. M. Dauchet, Transductions inversibles de forêts, Thèse 3ème cycle, Université de Lille (1975). Google Scholar
5. L. E. Dickson, Finiteness of the odd perfect and primitive abundant numbers with $n$ distinct prime factors, American Journal of Mathematics 35(4) (1913) 413–422. Crossref, Google Scholar
6. J. Engelfriet, Bottom-up and top-down tree transformations — A comparison, Mathematical Systems Theory 9(3) (1975) 198–231. Crossref, Google Scholar
7. J. Engelfriet, Z. Fülöp and H. Vogler, Bottom-up and top-down tree series transformations, Journal of Automata, Languages and Combinatorics 7(1) (2002) 11–70. Google Scholar
8. Z. Fülöp, A. Maletti and H. Vogler, Weighted extended tree transducers, Fundamenta Informaticae 111(2) (2011) 163–202. Crossref, Web of Science, Google Scholar
9. Z. Fülöp and H. Vogler, Syntax-Directed Semantics — Formal Models Based on Tree Transducers (Springer, 1998). Crossref, Google Scholar
10. Z. Fülöp and H. Vogler, Tree series transformations that respect copying, Theory of Computing Systems 36(3) (2003) 247–293. Crossref, Web of Science, Google Scholar
11. Z. Fülöp and H. Vogler, Weighted tree automata and tree transducers, Handbook of Weighted Automata, eds. M. Droste, W. Kuich and H. Vogler (Springer, 2009), pp. 313–403. Crossref, Google Scholar
12. J. S. Golan, Semirings and Their Applications (Kluwer Academic Publishers, 1999). Crossref, Google Scholar
13. J. Graehl, K. Knight and J. May, Training tree transducers, Computational Linguistics 34(3) (2008) 391–427. Crossref, Web of Science, Google Scholar
14. U. Hebisch and H. J. Weinert, Semirings — Algebraic Theory and Applications in Computer Science (World Scientific Publishing, 1998). Link, Google Scholar
15. D. Kirsten, The support of a recognizable series over a zero-sum free, commutative semiring is recognizable, Acta Cybernetica 20(2) (2011) 211–221. Crossref, Google Scholar
16. K. Knight and J. Graehl, An overview of probabilistic tree transducers for natural language processing, Proc. 6th Int. Conf. Intelligent Text Processing and Computational Linguistics, eds. A. F. Gelbukh, Lecture Notes in Computer Science 3406 (Springer, 2005), pp. 1–24. Google Scholar
17. P. Koehn, Statistical Machine Translation (Cambridge University Press, 2010). Google Scholar
18. W. Kuich, Tree transducers and formal tree series, Acta Cybernetica 14(1) (1999) 135–149. Google Scholar
19. A. Lagoutte and A. Maletti, Survey: Weighted extended top-down tree transducers — Part III: Composition, Proc. Workshop Algebraic Foundations in Computer Science, eds. W. Kuich and G. Rahonis, Lecture Notes in Computer Science, Vol. 7020 (Springer, 2011), pp. 272–308. Google Scholar
20. A. Maletti, Compositions of tree series transformations, Theorical Computer Science 366(3) (2006) 248–271. Crossref, Web of Science, Google Scholar
21. A. Maletti, Compositions of extended top-down tree transducers, Information and Computation 206(9–10) (2008) 1187–1196. Crossref, Web of Science, Google Scholar
22. A. Maletti, Survey: Weighted extended top-down tree transducers — Part I: Basics and expressive power, Acta Cybernetica 20(2) (2011) 223–250. Crossref, Google Scholar
23. A. Maletti, J. Graehl, M. Hopkins and K. Knight, The power of extended top-down tree transducers, SIAM Journal on Computing 39(2) (2009) 410–430. Crossref, Web of Science, Google Scholar
24. J. May, K. Knight and H. Vogler, Efficient inference through cascades of weighted tree transducers, Proc. 48th Ann. Meeting Association for Computational Linguistics, eds. J. Hajič, S. Carberry, S. Clark and J. Nivre (ACL, 2010), pp. 1058–1066. Google Scholar
25. M. Mohri, F. Pereira and M. Riley, Weighted finite-state transducers in speech recognition, Computer Speech & Language 16(1) (2002) 69–88. Crossref, Web of Science, Google Scholar
26. W. C. Rounds, Mappings and grammars on trees, Mathematical Systems Theory 4(3) (1970) 257–287. Crossref, Google Scholar
27. J. W. Thatcher, Generalized² sequential machine maps, Journal of Computer and System Sciences 4(4) (1970) 339–367. Crossref, Google Scholar
28. J. W. Thatcher, Tree automata: An informal survey, Currents in the Theory of Computing, ed. A. V. Aho (Prentice Hall, 1973), pp. 143–172. Google Scholar
29. K. Yamada and K. Knight, A decoder for syntax-based statistical MT, Proc. 40th Ann. Meeting Association for Computational Linguistics, eds. P. Isabelle, E. Charniak and D. Lin (ACL, 2002), pp. 303–310. Google Scholar