Abstract
A tree can be compressed into a DAG by sharing common subtrees. The resulting DAG is at most exponentially smaller than the original tree. Consider an attribute grammar that generates trees as output. It is well known that, given an input tree s, a DAG representation of the corresponding output tree can be computed in time linear in the size of s. A more powerful way of tree compression is to allow the sharing of tree patterns, i.e., internal parts of the tree. The resulting “sharing graph” is at most double-exponentially smaller than the original tree. Consider a macro tree transducer and an input tree s. The main result is that a sharing graph representation of the corresponding output tree can be computed in time linear in the size of s. A similar result holds for macro forest transducers which translate unranked forests, i.e., natural representations of XML documents.
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
Asperti, A., Guerrini, S.: The Optimal Implementation of Functional Programming Languages. In: Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (1998)
Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: Freytag, J.C., et al. (eds.) Proc. VLDB 2003. Morgan Kaufmann, San Francisco (2003)
Engelfriet, J.: Context-free graph grammars. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Springer, Heidelberg (1997)
Engelfriet, J., Heyker, L.: Context-free hypergraph grammars have the same term-generating power as attribute grammars. Acta Informatica 29, 161–210 (1992)
Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations. Inform. and Comput. 154, 34–91 (1999)
Engelfriet, J., Maneth, S.: Tree languages generated by context-free graph grammars. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) TAGT 1998. LNCS, vol. 1764, pp. 15–29. Springer, Heidelberg (2000)
Engelfriet, J., Maneth, S.: A comparison of pebble tree transducers with macro tree transducers. Acta Informatica 39, 613–698 (2003)
Engelfriet, J., Vogler, H.: Macro tree transducers. J. of Comp. Syst. Sci. 31, 71–146 (1985)
Engelfriet, J., Vogler, H.: The translation power of top-down tree-to-graph transducers. J. of Comp. Syst. Sci. 49, 258–305 (1994)
Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science – LICS 2003, pp. 188–197. IEEE, Los Alamitos (2003)
Gécseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Springer, Heidelberg (1997)
Guerrini, S.: A general theory of sharing graphs. TCS 227, 99–151 (1999)
Katajainen, J., Mäkinen, E.: Tree compression and optimization with applications. Intern. J. of Foundations of Comput. Sci. 1, 425–447 (1990)
Lamping, J.: An algorithm for optimal lambda calculus reductions. In: Proc. POPL 1990, pp. 16–30. ACM Press, New York (1990)
Lehman, E., Shelat, A.: Approximation algorithms for grammar-based compression. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 205–212. SIAM Press, Philadelphia (2002)
Liefke, H., Suciu, D.: XMill: An efficient compressor for xml data. In: Chen, W., et al. (eds.) Proc. ACM Conference on Management of Data, pp. 153–164. ACM, New York (2000)
Maneth, S.: The complexity of compositions of deterministic tree transducers. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol. 2556, pp. 265–276. Springer, Heidelberg (2002)
Maneth, S., Neven, F.: Recursive structured document transformations. In: Connor, R., Mendelzon, A. (eds.) DBPL 1999. LNCS, vol. 1949, pp. 80–98. Springer, Heidelberg (2000)
Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J. of Comp. Syst. Sci. 66, 66–97 (2003)
Perst, T., Seidl, H.: Macro forest transducers (to appear in IPL)
Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460–470. Springer, Heidelberg (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maneth, S., Busatto, G. (2004). Tree Transducers and Tree Compressions. In: Walukiewicz, I. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2004. Lecture Notes in Computer Science, vol 2987. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24727-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-24727-2_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21298-0
Online ISBN: 978-3-540-24727-2
eBook Packages: Springer Book Archive