Abstract
Higher-order recursion schemes are equations defining recursively new operations from given ones called “terminals”. Every such recursion scheme is proved to have a least interpreted semantics in every Scott’s model of λ-calculus in which the terminals are interpreted as continuous operations. For the uninterpreted semantics based on infinite λ-terms we follow the idea of Fiore, Plotkin and Turi and work in the category of sets in context, which are presheaves on the category of finite sets. Whereas Fiore et al proved that the presheaf F λ of λ-terms is an initial H λ -monoid, we work with the presheaf R λ of rational infinite λ-terms and prove that this is an initial iterative H λ -monoid. We conclude that every guarded higher-order recursion scheme has a unique uninterpreted solution in R λ .
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., Milius, S., Velebil, J.: Iterative algebras at work. Math. Structures Comput. Sci. 16, 1085–1131 (2006)
Adámek, J., Trnková, V.: Automata and algebras in a category. Kluwer Academic Publishers, Dordrecht (1990)
Aehlig, K.: A finite semantics of simply-typed lambda terms for infinite runs of automata. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 104–118. Springer, Heidelberg (2006)
Damm, W.: Higher-order program schemes and their languages. LNCS, vol. 48, pp. 51–72. Springer, Heidelberg (1979)
Fiore, M.: Second order dependently sorted abstract syntax. In: Proc. Logic in Computer Science 2008, pp. 57–68. IEEE Press, Los Alamitos (2008)
Fiore, M., Plotkin, G., Turi, D.: Abstract syntax and variable binding. In: Proc. Logic in Computer Science 1999, pp. 193–202. IEEE Press, Los Alamitos (1999)
Garland, S.J., Luckham, D.C.: Program schemes, recursion schemes and formal languages. J. Comput. Syst. Sci. 7, 119–160 (1973)
Guessarian, I.: Algebraic semantics. LNCS, vol. 99. Springer, Heidelberg (1981)
Janelidze, G., Kelly, G.M.: A note on actions of a monoidal category. Theory Appl. Categ. 9, 61–91 (2001)
Lack, S.: On the monadicity of finitary monads. J. Pure Appl. Algebra 140, 65–73 (1999)
Matthes, R., Uustalu, T.: Substitution in non-wellfounded syntax with variable binding. Theoret. Comput. Sci. 327, 155–174 (2004)
Milius, S.: Completely iterative algebras and completely iterative monads. Inform. and Comput. 196, 1–41 (2005)
Milius, S., Moss, L.: The category theoretic solution of recursive program schemes. Theoret. Comput. Sci. 366, 3–59 (2006); corrigendum 403, 409–415 (2008)
Miranda, G.: Structures generated by higher-order grammars and the safety constraint. Ph.D. Thesis, Merton College, Oxford (2006)
Power, J.: A unified category theoretical approach to variable binding. In: Proc. MERLIN 2003 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Adámek, J., Milius, S., Velebil, J. (2009). Semantics of Higher-Order Recursion Schemes. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds) Algebra and Coalgebra in Computer Science. CALCO 2009. Lecture Notes in Computer Science, vol 5728. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03741-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-03741-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03740-5
Online ISBN: 978-3-642-03741-2
eBook Packages: Computer ScienceComputer Science (R0)