We study the set $T_A$ of infinite binary trees with nodes labelled in a semiring $A$ from a coalgebraic perspective. We present coinductive definition and proof principles based on the fact that $T_A$ carries a final coalgebra structure. By viewing trees as formal power series, we develop a calculus where definitions are presented as behavioural differential equations. We present a general format for these equations that guarantees the existence and uniqueness of solutions. Although technically not very difficult, the resulting framework has surprisingly nice applications, which is illustrated by various concrete examples.

Additional Metadata
Keywords binary trees, bisimulation, coalgebra, rational expressions
ACM DATA STRUCTURES (acm E.1), COMPUTATION BY ABSTRACT DEVICES (acm F.1)
THEME Software (theme 1)
Publisher Academic Press
Journal Information and Computation
Citation
Silva, A.M, & Rutten, J.J.M.M. (2010). A coinductive calculus of binary trees. Information and Computation, 208(5), 578–593.