Abstract
Computations on trees form a classical topic in computing. These computations can be described in terms of machines (typically called tree transducers), or in terms of functions. This paper focuses on three flavors of bottom-up computations, of increasing generality. It brings categorical clarity by identifying a category of tree transducers together with two different behavior functors. The first sends a tree transducer to a coKleisli or biKleisli map (describing the contribution of each local node in an input tree to the global transformation) and the second to a tree function (the global tree transformation). The first behavior functor has an adjoint realization functor, like in Goguen’s early work on automata. Further categorical structure, in the form of Hughes’s Arrows, appears in properly parameterized versions of these structures.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications. Book draft (2005)
Engelfriet, J.: Bottom-up and top-down tree transformations—a comparison. Math. Syst. Theory 9(3), 198–231 (1975)
Goguen, J.: Minimal realization of machines in closed categories. Bull. Amer. Math. Soc. 78(5), 777–783 (1972)
Heunen, C., Jacobs, B.: Arrows, like monads, are monoids. In: Brookes, S., Mislove, M. (eds.) Proc. of 22nd Conf. on Math. Found. of Program. Semantics, MFPS-XXII. Electr. Notes in Theor. Comput. Sci., vol. 158, pp. 219–236. Elsevier, Amsterdam (2006)
Hughes, J.: Generalising monads to arrows. Sci. of Comput. Program. 37(1–3), 67–111 (2000)
Jacobs, B.: Categorical Logic and Type Theory. North-Holland, Amsterdam (1999)
Jacobs, B., Hasuo, I.: Freyd is Kleisli, for arrows. In: McBride, C., Uustalu, T. (eds.) Proc. of Wksh. on Mathematically Structured Functional Programming, MSFP ’06, Electron. Wkshs. in Comput. Sci., BCS (2006)
Power, J., Robinson, E.: Premonoidal categories and notions of computation. Math. Struct. in Comput. Sci. 7(5), 453–468 (1997)
Rosebrugh, R.D., Sabadini, N., Walters, R.F.C.: Minimal realization in bicategories of automata. Math. Struct. in Comput. Sci. 8(2), 93–116 (1998)
Rounds, W.C.: Mappings and grammars on trees. Math. Syst. Theory 4(3), 257–287 (1970)
Thatcher, J.W.: Generalized sequential machine maps. J. Comput. Syst. Sci. 4(4), 339–367 (1970)
Uustalu, T., Vene, V.: Comonadic functional attribute evaluation. In: van Eekelen, M. (ed.) Trends in Functional Programming 6, Intellect, pp. 145–162 (2007)
Uustalu, T., Vene, V.: The essence of dataflow programming. In: Horváth, Z. (ed.) CEFP 2005. LNCS, vol. 4164, pp. 135–167. Springer, Heidelberg (2006)
Uustalu, T., Vene, V.: The dual of substitution is redecoration. In: Hammond, K., Curtis, S. (eds.) Trends in Functional Programming 3, Intellect, pp. 99–110 (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hasuo, I., Jacobs, B., Uustalu, T. (2007). Categorical Views on Computations on Trees (Extended Abstract). In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73420-8_54
Download citation
DOI: https://doi.org/10.1007/978-3-540-73420-8_54
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73419-2
Online ISBN: 978-3-540-73420-8
eBook Packages: Computer ScienceComputer Science (R0)