Rot, Jurriaan Cornelis · Leiden Repository (Leiden University) · 2015
<p>Coinduction, the dual of induction, is a fundamental principle for defining infinite objects and proving properties about them. The broad applicability and rapidly increasing interest in coinductive techniques is based on the theory of coalgebras, which allows one to understand and prove properties of state-based models of computation at a high level of abstraction. \n In this thesis we develop methods that simplify and enhance coinductive reasoning, with coalgebra as the framework of choice to obtain generally applicable techniques. In the first part, we introduce a coalgebraic framework of enhanced coinductive proof methods, \n which is applicable to a wide range of coinductive predicates and a wide range of state-based systems. In the second part, we propose enhancements to coinductive definition techniques based on the theory of mathematical operational semantics.<br /></p>
Cited by 0Open access
Falk Bartels · 2002
this paper express that the above principles work under dierent additional assumptions which are needed to show that the large system can actually be constructed inside the category. The basic Theorem requires the existence of countable coproducts. Later we also present a variant where the functor T comes a as a monad, the functor F is taken from a copointed functor, and the distributive law is assumed to interact nicely with this additional structure (i.e. should be a distributive law of the monad over the copointed functor, see again (Lenisa et al., 2000)). As a trivial instance of the new framework one recovers the basic coiteration schema and the standard coinduction proof principle. More interesting settings for T and yield the known schemata of primitive corecursion and the dual of course-of-value iteration mentioned above. In some more detail we explain another instance of the framework which deals with certain sets of auxiliary operators, like e.g. parallel and sequential composition for labelled transition systems. More precisely, it can handle such operators which are denable by a format introduced by Turi and Plotkin (Turi and Plotkin, 1997) as a categorical generalization of the known GSOS rule format (Bloom et al., 1995). On the one hand one obtains denition principles guaranteeing unique solutions for (guarded) recursive equations involving these operators, one the other hand this leads to a proof principle up-to-context for contexts built from them. 1.1. Related Work A rst proposal for a parameterised description covering several extended coinduction principles on a categorical level has been made by Lenisa in the course of her comparison of set-theoretic and coalgebraic (categorical) formulations of coinduction (Lenisa, 1999). Recently but ind...
Cited by 0
Falk Bartels · Mathematical Structures in Computer Science · 2003
We introduce the , while still giving rise to a proof technique for bisimilarity. We first present a theorem showing the validity of the resulting definition and proof principles for categories with countable coproducts.Our approach gives a unifying categorical presentation and justification of several extensions of the basic coinduction schemata that have been treated separately before, and some only for specific types of system. As examples, the duals of primitive recursion and course-of-value iteration, which are known extensions of coiteration, arise as instances of our framework.Moreover, we derive schemata involving auxiliary operators definable with GSOS-style specifications such as addition of streams, regular operators on languages, or parallel and sequential composition of processes. The argument is based on a variation of the theory in the setting of monads and copointed functors. The schemata justify guarded recursive definitions and an up-to-context proof technique for operators of the type mentioned. The latter can ease bisimilarity proofs considerably.
Cited by 44
Dexter Kozen Alex, Ra Silva · 2012
Induction is a well-established proof principle that is taught in most undergraduate programs in mathematics and computer science. In computer science, it is used primarily to reason about inductively-defined datatypes such as finite lists, finite trees, and the natural numbers. Coinduction is the dual principle that can be used to reason about coinductive datatypes such as infinite streams or trees, but it is not as widespread or as well understood. In this paper, we illustrate through several examples the use of coinduction in informal mathematical arguments. Our aim is to promote the principle as a useful tool for the working mathematician and to bring it to a level of familiarity on par with induction. We show that coinduction is not only about bisimilarity and equality of behaviors, but also applicable to a variety of functions and relations defined on coinductive datatypes. 1
Cited by 0
Norvig, Peter, Goguen, Joseph, Rosu, Grigore · NASA STI Repository (National Aeronautics and Space Administration)
Circular coinduction is a technique for behavioral reasoning that extends cobasis coinduction to specifications with circularities. Because behavioral satisfaction is not recursively enumerable, no algorithm can work for every behavioral statement. However. algorithms using circular coinduction can prove every practical behavioral result that we know. This paper proves the correctness of circular coinduction and some consequences.
Cited by 0Open access
Kozen, Dexter, Silva, Alexandra · eCommons (Cornell University) · 2012
Induction is a well-established proof principle that is taught in most undergraduate programs in mathematics and computer science. In computer science, it is used primarily to reason about inductively-defined datatypes such as finite lists, finite trees, and the natural numbers. Coinduction is the dual principle that can be used to reason about coinductive datatypes such as infinite streams or trees, but it is not as widespread or as well understood. In this paper, we illustrate through several examples the use of coinduction in informal mathematical arguments. Our aim is to promote the principle as a useful tool for the working mathematician and to bring it to a level of familiarity on par with induction. We show that coinduction is not only about bisimilarity and equality of behaviors, but also applicable to a variety of functions and relations defined on coinductive datatypes.
Cited by 0Open access
Falk Bartels · Electronic Notes in Theoretical Computer Science · 2001
We introduce the λ-coiteration schema for a distributive law λ of a functor T over a functor F. Under certain conditions it can be shown to uniquely characterise functions into the carrier of a final F-coalgebra, generalising the basic coiteration schema as given by finality. The duals of primitive recursion and course-of-value iteration, which are known extensions of coiteration, arise as instances of our framework. One can furthermore obtain schemata justifying recursive specifications that involve operators such as addition of power series, regular operators on languages, or parallel and sequential composition of processes. Next, the same type of distributive law λ is used to generalise coinductive proof techniques. To this end, we introduce the notion of a λ-bisimulation relation. It specialises to what could be called bisimulation up-to-equality or bisimulation up-to-context for contexts built from operators of the type mentioned above. We state that every such relation is contained in some larger conventional bisimulation and demonstrate that this principle leads to simpler bisimilarity proofs using less complex relations.
Cited by 54Open access
Bertot, Yves · HAL (Le Centre pour la Communication Scientifique Directe) · 2005
Cited by 0Open access
Yves Bertot · 2005
When providing a collection of constructors to define an inductive type, we actually also define a dual operation: a destructor. This destructor is always defined using the same structure of pattern-matching, so that we have a tendency to forget that we do extend the “pattern-matching ” capability with a new destructor at each definition. Constructors and destructors play a dual role in the definition of inductive types. Constructors produce elements of the inductive type, destructors consume elements of the inductive type. The inductive type itself is defined as the smallest collection of elements that is stable with respect to the constructors: it must contain all constants that are declared to be in the inductive type and all results of the constructors when the arguments of these constructors are already found to be in the inductive type. When considering structural recursion, recursive definitions are functions that consume elements of the inductive type. The discipline of structural recursion imposes that recursive calls consume data that is obtained through the destructor. The inductive type uses the constructors and destructors in a specific way. Co-inductive
Cited by 0
Pous, Damien · SPIRE - Sciences Po Institutional REpository · 2016
Coinductive predicates are greatest fixpoints of monotone functions.The `companion' makes it possible to enhance the associated coinduction scheme.This library provides a formalisation on enhancements based on the companion, as well as tactics in making it straightforward to perform proofs by enhanced coinduction.
Cited by 0
J.J.M.M. Rutten, Marta Kwiatkowska, Gethin Norman et al. · CRM monograph series · 2004
Cited by 1
Robin Cockett, Luigi Santocanale · Electronic Notes in Theoretical Computer Science · 2003
We investigate the reasons for which the existence of certain right adjoints implies the existence of some final coalgebras, and vice-versa. In particular we prove and discuss the following theorem which has been partially available in the literature: let F ⊣ G be a pair of adjoint functors, and suppose that an initial algebra F̂(X) of the functor H(Y) = X + F(Y) exists; then a right adjoint G̃(X) to F̂(X) exists if and only if a final coalgebra Ǧ(X) of the functor K(Y) = X × G(Y) exists. Motivated by the problem of understanding the structures that arise from initial algebras, we show the following: if F is a left adjoint with a certain commutativity property, then an initial algebra of H(Y) = X + F(Y) generates a subcategory of functors with inductive types where the functorial composition is constrained to be a Cartesian product.
Cited by 4Open access
Răzvan Diaconescu · Information and Computation · 2010
Cited by 6
Dexter Kozen, Nicholas Ruozzi · Logical Methods in Computer Science · 2009
Metric coinduction is a form of coinduction that can be used to establish properties of objects constructed as a limit of finite approximations. One can prove a coinduction step showing that some property is preserved by one step of the approximation process, then automatically infer by the coinduction principle that the property holds of the limit object. This can often be used to avoid complicated analytic arguments involving limits and convergence, replacing them with simpler algebraic arguments. This paper examines the application of this principle in a variety of areas, including infinite streams, Markov chains, Markov decision processes, and non-well-founded sets. These results point to the usefulness of coinduction as a general proof technique.
Cited by 11Open access
Kozen, Dexter, Ruozzi, Nicholas · arXiv (Cornell University) · 2009
Metric coinduction is a form of coinduction that can be used to establish properties of objects constructed as a limit of finite approximations. One can prove a coinduction step showing that some property is preserved by one step of the approximation process, then automatically infer by the coinduction principle that the property holds of the limit object. This can often be used to avoid complicated analytic arguments involving limits and convergence, replacing them with simpler algebraic arguments. This paper examines the application of this principle in a variety of areas, including infinite streams, Markov chains, Markov decision processes, and non-well-founded sets. These results point to the usefulness of coinduction as a general proof technique.
Cited by 0Open access
Marina Lenisa · 1999
Cited by 0
Luca Ciccone, Francesco Dagnino, Elena Zucca · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
We provide an Agda library for inference systems, also supporting their recent generalization allowing flexible coinduction, that is, interpretations which are neither inductive, nor purely coinductive. A specific inference system can be obtained as an instance by writing a set of meta-rules, in an Agda format which closely resembles the usual one. In this way, the user gets for free the related properties, notably the inductive and coinductive intepretation and the corresponding proof principles. Moreover, a significant modularity is achieved. Indeed, rather than being defined from scratch and with a built-in interpretation, an inference system can also be obtained by composition operators, such as union and restriction to a smaller universe, and its semantics can be modularly chosen as well. In particular, flexible coinduction is obtained by composing in a certain way the interpretations of two inference systems. We illustrate the use of the library by several examples. The most significant one is a big-step semantics for the λ-calculus, where flexible coinduction allows to obtain a special result (∞) for all and only the diverging computations, and the proof of equivalence with small-step semantics is carried out by relying on the proof principles offered by the library.
Cited by 4Open access
Alberto Ciaffaglione · Science of Computer Programming · 2016
Cited by 5
Per Martin-Löf, Giovanni Sambin · 2025
Cited by 0
Luke Evans Simon · 2006
Cited by 0