Abstract
In formal language theory, James Rogers published a series of innovative papers generalising strings and trees to higher dimensions. Motivated by applications in linguistics, his goal was to smoothly extend the core theory of the formal languages of strings and trees to higher dimensions.
Rogers’ definitions rely on a specific representation of higher dimensional trees. This paper presents an alternative approach which focusses more on their universal properties and is based upon category theory, algebras, coalgebras and containers. Our approach reveals that Rogers’ trees are canonical constructions which are also particularly beautiful. We also provide new theoretical results concerning higher dimensional trees. Finally, we provide evidence for our devout conviction that clean mathematical theories provide the basis for clean implementations by indicating how our abstract presentation will make computing with higher dimensional trees easier.
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
Adámek, J., Trnková, V.: Automata and Algebras in Categories. Kluwer Academic Publishers, Dordrecht (1990)
Arbib, M.A., Manes, E.G.: Machines in a category: An expository introduction. SIAM Review 16 (1974)
Arbib, M.A., Manes, E.G.: Adjoint machines, state-behaviour machines, and duality. Journ. of Pure and Applied Algebra 6 (1975)
Arbib, M.A., Manes, E.G.: Fuzzy machines in a category. Bull. Austral. Math. Soc. 13 (1975)
Barr, M.: Relational algebras. LNM 137 (1970)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997), Available online.
de Moor, O.: Inductive data types for predicate transformers. Information Processing Letters 43(3), 113–118 (1992)
Ghani, N., Abbott, M., Altenkirch, T.: Containers - constructing strictly positive types. Theoretical Computer Science 341(1), 3–27 (2005)
Ghani, N., Lüth, C., de Marchi, F, Power, J.: Dualizing initial algebras. Mathematical Structures in Computer Science 13(1), 349–370 (2003)
Hasuo, I., Jacobs, B., Sokolova, A.: Generic trace theory. In: International Workshop on Coalgebraic Methods in Computer Science (CMCS 2006). Elect. Notes in Theor. Comp. Sci. vol. 164, pp. 47–65. Elsevier, Amsterdam (2006)
Rogers, J.: Syntactic structures as multi-dimensional trees. Research on Language and Computation 1(3-4), 265–305 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ghani, N., Kurz, A. (2007). Higher Dimensional Trees, Algebraically. In: Mossakowski, T., Montanari, U., Haveraaen, M. (eds) Algebra and Coalgebra in Computer Science. CALCO 2007. Lecture Notes in Computer Science, vol 4624. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73859-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-73859-6_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73857-2
Online ISBN: 978-3-540-73859-6
eBook Packages: Computer ScienceComputer Science (R0)