Abstract
In this work we present a modular theory of the coalgebras and bisimulation in the intensional type theory implemented in coq. On top of that we build the theory of weakly final coalgebras and develop the λ-coiteration scheme, thereby extending the class of specifications definable in coq. We provide an instantiation of the theory for the coalgebra of streams and show how some of the productive specifications violating the guardedness condition of coq can be formalised using our library.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Abel, A.: Semi-continuous sized types and termination. Logic. Methods in Comput. Sci. 4(2:3), 1–33 (2008)
Altenkirch, T., McBride, C., Swierstra, W.: Observational equality, now! In: Stump, A., Xi, H. (eds.) Proc. of PLPV 2007, pp. 57–68. ACM Press, New York (2007)
Bartels, F.: Generalised coinduction. In: Corradini, A., Lenisa, M., Montanari, U. (eds.) Proc. of CMCS 2001. ENTCS, vol. 44(1), pp. 67–87. Elsevier, Amsterdam (2001)
Bartels, F.: On Generalised Coinduction and Probabilistic specification Formats: Distributive laws in coalgebraic modelling. PhD thesis, Vrije Universiteit Amsterdam (2004)
Bertot, Y., Komendantskaya, E.: Inductive and coinductive components of corecursive functions in coq. In: Adámek, J., Kupke, C. (eds.) Proc. of CMCS 2008. ENTCS, vol. 203(5), pp. 25–47. Elsevier, Amsterdam (2008)
Bertot, Y., Komendantskaya, E.: Using structural recursion for corecursion. Technical report, INRIA (September 2008), http://hal.inria.fr/inria-00322331/ (cited 18 Febrary 2009)
Cancila, D., Honsell, F., Lenisa, M.: Generalized coiteration schemata. In: Gumm, P. (ed.) Proc. of CMCS 2003. ENTCS, vol. 82(1), pp. 76–93. Elsevier, Amsterdam (2003)
The Coq Development Team. Reference Manual, Version 8.2. LogiCal Project (July 2006), http://coq.inria.fr/V8.2/doc/html/refman/ (cited 18 February 2009)
Coquand, T.: Infinite objects in type theory. In: Barendregt, H., Nipkow, T. (eds.) TYPES 1993. LNCS, vol. 806, pp. 62–78. Springer, Heidelberg (1994)
Di Gianantonio, P., Miculan, M.: A unifying approach to recursive and co-recursive definitions. In: Geuvers, H., Wiedijk, F. (eds.) TYPES 2002. LNCS, vol. 2646, pp. 148–161. Springer, Heidelberg (2003)
Giménez, E.: Un Calcul de Constructions Infinies et son Application a la Verification des Systemes Communicants. PhD thesis PhD 96-11, Laboratoire de l’Informatique du Parallélisme, Ecole Normale Supérieure de Lyon (December 1996)
Hancock, P., Setzer, A.: Interactive programs and weakly final coalgebras in dependent type theory. In: Crosilla, L., Schuster, P. (eds.) From Sets and Types to Topology and Analysis. Towards Practicable Foundations for Constructive Mathematics. Oxford Logic Guides, vol. 48, pp. 115–134. Oxford University Press, Oxford (2005)
Hofmann, M.: Conservativity of equality reflection over intensional type theory. In: Berardi, S., Coppo, M. (eds.) TYPES 1995. LNCS, vol. 1158, pp. 153–164. Springer, Heidelberg (1996)
Huet, G., Saïbi, A.: Constructive category theory. In: Plotkin, G.D., Stirling, C., Tofte, M. (eds.) Proof, Language, and Interaction, Essays in Honour of Robin Milner, pp. 239–276. MIT Press, Cambridge (2000)
Matthes, R.: An induction principle for nested datatypes in intensional type theory. J. Funct. Programming, 29 page (to appear, 2009), http://www.irit.fr/~Ralph.Matthes/papers/VNestITTfinal.pdf (cited 18 February 2009)
McBride, C.: Dependently Typed Programs and their Proofs. PhD thesis, University of Edinburgh (1999)
McIlroy, M.D.: The music of streams. Inform. Process. Lett. 77(2–4), 189–195 (2001)
Michelbrink, M.: Interfaces as functors, programs as coalgebras - a final coalgebra theorem in intensional type theory. Theoret. Comput. Sci. 360(1–3), 415–439 (2006)
Niqui, M.: Files for Coq v. 8.2 (October 2008), http://coq.inria.fr/contribs/Coalgebras (cited 18 February 2009)
Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249(1), 3–80 (2000)
Rutten, J.J.M.M.: A coinductive calculus of streams. Math. Structures Comput. Sci. 15(1), 93–147 (2005)
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
Niqui, M. (2009). Coalgebraic Reasoning in Coq: Bisimulation and the λ-Coiteration Scheme. In: Berardi, S., Damiani, F., de’Liguoro, U. (eds) Types for Proofs and Programs. TYPES 2008. Lecture Notes in Computer Science, vol 5497. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02444-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-02444-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02443-6
Online ISBN: 978-3-642-02444-3
eBook Packages: Computer ScienceComputer Science (R0)