Abstract
We study normalization of deterministic sequential top-down tree-to-word transducers (stWs), that capture the class of deterministic top-down nested-word to word transducers. We identify the subclass of earliest stWs (estWs) that yield unique normal forms when minimized. The main result of this paper is an effective normalization procedure for stWs. It consists of two stages: we first convert a given stW to an equivalent estW, and then, we minimize the estW.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1102–1114. Springer, Heidelberg (2005)
Berstel, J., Boasson, L.: Transductions and context-free languages. Teubner Studienbucher (1979)
Choffru, C.: Contribution à l’étude de quelques familles remarquables de fonctions rationnelles. PhD thesis, Université de Paris VII (1978)
Choffrut, C.: Minimizing subsequential transducers: a survey. Theoretical Computer Science 292(1), 131–143 (2003)
Engelfriet, J., Maneth, S., Seidl, H.: Deciding equivalence of top-down XML transformations in polynomial time. Journal of Computer and System Science 75(5), 271–286 (2009)
Filiot, E., Raskin, J.F., Reynier, P.A., Servais, F., Talbot, J.M.: Properties of visibly pushdown transducers. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 355–367. Springer, Heidelberg (2010)
Friese, S., Seidl, H., Maneth, S.: Minimization of deterministic bottom-up tree transducers. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 185–196. Springer, Heidelberg (2010)
Griffiths, T.V.: The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. Journal of the ACM 15(3), 409–413 (1968)
Gurari, E.M.: The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM Journal on Computing 11(3), 448–452 (1982)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (2001)
Lemay, A., Maneth, S., Niehren, J.: A learning algorithm for top-down xml transformations. In: ACM Symposium on Principles of Database Systems (PODS), pp. 285–296 (2010)
Lothaire, M. (ed.): Combinatorics on Words, 2nd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997)
Maneth, S.: Models of Tree Translation. PhD thesis, Leiden University (2003)
Martens, W., Neven, F., Gyssens, M.: Typechecking top-down XML transformations: Fixed input or output schemas. Information and Computation 206(7), 806–827 (2008)
Raskin, J.-F., Servais, F.: Visibly pushdown transducers. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 386–397. Springer, Heidelberg (2008)
Staworko, S., Laurence, G., Lemay, A., Niehren, J.: Equivalence of deterministic nested word to word transducers. In: Kutyłowski, M., Charatonik, W., Gębala, M. (eds.) FCT 2009. LNCS, vol. 5699, pp. 310–322. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Laurence, G., Lemay, A., Niehren, J., Staworko, S., Tommasi, M. (2011). Normalization of Sequential Top-Down Tree-to-Word Transducers. In: Dediu, AH., Inenaga, S., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2011. Lecture Notes in Computer Science, vol 6638. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21254-3_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-21254-3_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21253-6
Online ISBN: 978-3-642-21254-3
eBook Packages: Computer ScienceComputer Science (R0)