Abstract
A tree transducer with origin translates an input tree into a pair of output tree and origin info. The origin info maps each node in the output tree to the unique input node that created it. In this way, the implementation of the transducer becomes part of its semantics. We show that the landscape of decidable properties changes drastically when origin info is added. For instance, equivalence of nondeterministic top-down and MSO transducers with origin is decidable. Both problems are undecidable without origin. The equivalence of deterministic top-down tree-to-string transducers is decidable with origin, while without origin it is a long standing open problem. With origin, we can decide if a deterministic macro tree transducer can be realized by a deterministic top-down tree transducer; without origin this is an open problem.
The authors are grateful to Joost Engelfriet for his remarks for improvement and correction on an earlier version of this paper. This work has been carried out thanks to the support of the ARCHIMEDE Labex (ANR-11-LABX-0033) and the A*MIDEX project (ANR-11-IDEX-0001-02) funded by the “Investissements d’Avenir” French Government program, managed by the French National Research Agency (ANR) and by the PEPS project “Synthesis of Stream Processors” funded by CNRS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andre, Y., Bossut, F.: On the equivalence problem for letter-to-letter top-down tree transducers. Theor. Comput. Sci. 205(1–2), 207–229 (1998)
Benedikt, M., Engelfriet, J., Maneth, S.: Determinacy and rewriting of top-down and MSO tree transformations. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 146–158. Springer, Heidelberg (2013)
Bojańczyk, M.: Transducers with origin information. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 26–37. Springer, Heidelberg (2014)
Braune, F., Seemann, N., Quernheim, D., Maletti, A.: Shallow local multi-bottom-up tree transducers in statistical machine translation. In: ACL, pp. 811–821 (2013)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Löding, C., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007)
Drewes, F., Engelfriet, J.: Decidability of the finiteness of ranges of tree transductions. Inf. Comput. 145(1), 1–50 (1998)
Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. In: Book, R. (ed.) Formal language theory; perspectives and open problems. Academic Press, New York (1980)
Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations. Inf. Comput. 154(1), 34–91 (1999)
Engelfriet, J., Maneth, S.: Macro tree translations of linear size increase are MSO definable. SIAM J. Comput. 32(4), 950–1006 (2003)
Engelfriet, J., Maneth, S.: The equivalence problem for deterministic MSO tree transducers is decidable. Inf. Process. Lett. 100(5), 206–212 (2006)
Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines. J. Comput. Syst. Sci. 20(2), 150–202 (1980)
Ésik, Z.: Decidability results concerning tree transducers I. Acta Cybern. 5(1), 1–20 (1980)
Fülöp, Z., Vogler, H.: Syntax-Directed Semantics - Formal Models Based on Tree Transducers. Springer, Monographs in Theoretical Computer Science. An EATCS Series (1998)
Griffiths, T.V.: The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. J. ACM 15(3), 409–413 (1968)
Hakuta, S., Maneth, S., Nakano, K., Iwasaki, H.: Xquery streaming by forest transducers. In: ICDE, pp. 952–963 (2014)
Küsters, R., Wilke, T.: Transducer-based analysis of cryptographic protocols. Inf. Comput. 205(12), 1741–1776 (2007)
A. Lemay, S. Maneth, and J. Niehren. A learning algorithm for top-down XML transformations. In: PODS, pp. 285–296 (2010)
Maletti, A.: Tree transformations and dependencies. In: MOL, pp. 1–20 (2011)
Maletti, A., Graehl, J., Hopkins, M., Knight, K.: The power of extended top-down tree transducers. SIAM J. Comput. 39(2), 410–430 (2009)
Maneth, S.: Equivalence problems for tree transducers (survey). In: AFL, pp. 74–93 (2014)
Matsuda, K., Inaba, K., Nakano, K.: Polynomial-time inverse computation for accumulative functions with multiple data traversals. In: PEPM, pp. 5–14 (2012)
Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J. Comput. Syst. Sci. 66(1), 66–97 (2003)
Rounds, W.C.: Mappings and grammars on trees. Math. Syst. Th. 4(3), 257–287 (1970)
Thatcher, J.W.: Generalized sequential machine maps. JCSS 4(4), 339–367 (1970)
van Deursen, A., Klint, P., Tip, F.: Origin tracking. J. Symb. Comput. 15(5/6), 523–545 (1993)
Voigtländer, J., Hu, Z., Matsuda, K., Wang, M.: Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins. J. Funct. Program. 23(5), 515–551 (2013)
Voigtländer, J., Kühnemann, A.: Composition of functions with accumulating parameters. J. Funct. Program. 14(3), 317–363 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Filiot, E., Maneth, S., Reynier, PA., Talbot, JM. (2015). Decision Problems of Tree Transducers with Origin. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-662-47666-6_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47665-9
Online ISBN: 978-3-662-47666-6
eBook Packages: Computer ScienceComputer Science (R0)