English
Coinduction has come to play an ever more important role in computer science, for the specification of infinite data types such as streams (infinite sequences) and, more generally automata with infinite behaviour. However, a common understanding of coinductive definition and proof principles is still lacking, very much in contrast with the situation for induction, where principles such as well-founded induction and recursion are common knowledge. This project seeks to develop elementary and user-friendly definition and proof techniques for coinduction. We will work in the recently introduced formalism of behavioural differential equations (BDEs), which offer a good compromise between generality and practicality, as is illustrated by existing applications in automata theory, control theory, stream processing, concurrency, and security. In close analogy to mathematical analysis, BDEs specify behaviour in the form of a differential equation. Our main challenge will be the identification of conditions on and formats for such BDEs guaranteeing their well-definedness and the computability of their solution. Our approach will combine coalgebra, where the notion of BDEs was invented, with term rewriting and theorem proving. Term rewriting techniques on productivity and termination have recently been shown to be relevant for solving BDEs. Proof assistants such as COQ and CIRC will be useful for proving properties of solutions such as uniqueness and equivalence. Our results, which will consist of concrete formats for BDEs together with algorithms for solving them, will be tested along the way on some of the recent applications of BDEs, notably, in stream processing networks.
