Picture of wind turbine against blue sky

Open Access research with a real impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs.

The Energy Systems Research Unit (ESRU) within Strathclyde's Department of Mechanical and Aerospace Engineering is producing Open Access research that can help society deploy and optimise renewable energy systems, such as wind turbine technology.

Explore wind turbine research in Strathprints

Explore all of Strathclyde's Open Access research content

Indexed induction and coinduction, fibrationally.

Ghani, Neil and Johann, Patricia and Fumex, Clement (2011) Indexed induction and coinduction, fibrationally. In: Algebra and coalgebra in computer science. Lecture Notes in Computer Science . Springer, pp. 176-191. ISBN 9783642229435

[img]
Preview
PDF
ghani_calco11.pdf - Draft Version

Download (542kB) | Preview

Abstract

This paper extends the fibrational approach to induction and coinduction pioneered by Hermida and Jacobs, and developed by the current authors, in two key directions. First, we present a sound coinduction rule for any data type arising as the final coalgebra of a functor, thus relaxing Hermida and Jacobs’ restriction to polynomial data types. For this we introduce the notion of a quotient category with equality (QCE), which both abstracts the standard notion of a fibration of relations constructed from a given fibration, and plays a role in the theory of coinduction dual to that of a comprehension category with unit (CCU) in the theory of induction. Second, we show that indexed inductive and coinductive types also admit sound induction and coinduction rules. Indexed data types often arise as initial algebras and final coalgebras of functors on slice categories, so our key technical results give sufficent conditions under which we can construct, from a CCU (QCE) U : E -> B, a fibration with base B/I that models indexing by I and is also a CCU (QCE).