Special Issue: 8th International Conference on Developments in Language Theory (DLT '04)No Access

RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA

ANDREAS MALETTI

Fakultät Informatik, Technische Universität Dresden, D–01062 Dresden, Germany

Financially supported by the German Research Foundation (DFG) under grant GK 334/3 and by the Freunde und Förderer der Informatik an der TU-Dresden e. V.

Search for more papers by this author

https://doi.org/10.1142/S012905410500325XCited by:11 (Source: Crossref)

Abstract

Bottom-up tree series transducers (tst) over the semiring are implemented with the help of bottom-up weighted tree automata (wta) over an extension of . Therefore bottom-up -weighted tree automata (-wta) with a distributive Ω-algebra are introduced. A -wta is essentially a wta but uses as transition weight an operation symbol of the Ω-algebra instead of a semiring element. The given tst is implemented with the help of a -wta, essentially showing that -wta are a joint generalization of tst (using IO-substitution) and wta. Then a semiring and a wta are constructed such that the wta computes a formal representation of the semantics of the -wta. The applicability of the obtained presentation result is demonstrated by deriving a pumping lemma for deterministic finite -wta from a known pumping lemma for deterministic finite wta. Finally, it is observed that the known decidability results for emptiness cannot be applied to obtain decidability of emptiness for finite -wta. Thus with help of a weaker version of the derived pumping lemma, decidability of the emptiness problem for finite -wta is shown under mild conditions on .

This is an extended and revised version of: A. Maletti, "Relating Tree Series Transducers and Weighted Tree Automata," in Proc. 8th Int. Conf. on Developments in Language Theory, eds. C. Calude, E. Calude and M. J. Dinneen, LNCS 3340 (Springer, Heidelberg, 2004) pp. 321–333.

Keywords:

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

References

J. Berstel , Transductions and Context-Free Languages ( Teubner , Stuttgart , 1979 ) . Crossref, Google Scholar
J. Berstel and C. Reutenauer, Theoret. Comput. Sci. 18, 115 (1982). Crossref, Web of Science, Google Scholar
B. Borchardt, Acta Cybernet. 16, 509 (2004). Google Scholar
B. Borchardt and H. Vogler, J. Autom. Lang. Comb. 8, 417 (2003). Web of Science, Google Scholar
S. Bozapalidis, Theory Comput. Syst. 32, 1 (1999). Crossref, Web of Science, Google Scholar
S. Bozapalidis, Inform. and Comput. 169, 186 (2001). Crossref, Web of Science, Google Scholar
S. Bozapalidis and G. Rahonis, Weighted Automata: Theory and Applications, eds. M. Droste and H. Vogler (Technische Universität Dresden, 2004) p. 34. Google Scholar
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, "Tree automata—techniques and applications," 1997. Available at: http://www.grappa.univ-lille3.fr/tata . Google Scholar
S. Eilenberg , Automata, Languages, and Machines—Volume A , Pure and Applied Mathematics 59 ( Academic Press , Orlando , 1974 ) . Google Scholar
J. Engelfriet, Z. Fülöp and H. Vogler, J. Autom. Lang. Comb. 7, 11 (2002). Web of Science, Google Scholar
Z. Ésik and W. Kuich, J. Autom. Lang. Comb. 8, 219 (2003). Google Scholar
Z. Fülöp and H. Vogler, Theory Comput. Syst. 36, 247 (2003). Crossref, Web of Science, Google Scholar
F. Gécseg and M. Steinby , Tree Automata ( Akadémiai Kiadó , Budapest , 1984 ) . Google Scholar
F. Gécseg and M. Steinby, Handbook of Formal Languages 3, eds. G. Rozenberg and A. Salomaa (Springer, Heidelberg, 1997) pp. 1–68. Crossref, Google Scholar
J. A. Goguenet al., J. ACM 24, 68 (1977). Crossref, Web of Science, Google Scholar
W. Kuich, Formal power series over trees, Proc. 3rd Int. Conf. on Developments in Language Theory, ed. S. Bozapalidis (Aristotle University of Thessaloniki, 1977) pp. 61–101. Google Scholar
W. Kuich, Acta Cybernet. 14, 135 (1999). Google Scholar
W. Kuich and A. Salomaa , Semirings, Automata, Languages , EATCS Monographs on Theoretical Computer Science 5 ( Springer , Heidelberg , 1986 ) . Crossref, Google Scholar
A. Maletti, Relating tree series transducers and weightde tree automata, Proc. 8th Int. Conf. on Developments in Language Theory, LNCS 3340, eds. C. Calude, E. Calude and M. J. Dinneen (Springer, Heidelberg, 2004) pp. 321–333. Google Scholar
W. C. Rounds, Math. Syst. Theory 4, 257 (1970). Crossref, Google Scholar
G. Rozenberg and A. Salomaa (eds.) , Handbook of Formal Languages 1 ( Springer , Heidelberg , 1997 ) . Crossref, Google Scholar
M. P. Schützenberger, Certain elementary families of automata, Proc. of Symposium on Mathematical Theory of Automata (Polytechnic Institute of Brooklyn, 1962) pp. 139–153. Google Scholar
J. W. Thatcher, J. Comput. System Sci. 4, 339 (1970). Crossref, Web of Science, Google Scholar