Michael Brandt, Fritz Henglein. Coinductive axiomatization of recursive type equality and subtyping. Fundamenta Informaticae, Invited submission to special issue featuring a selection of contributions to the 3d Int'l Conf. on Typed Lambda Calculi and Applications (TLCA), 1997, 33(4):309-338, 1998.
Download paper:
Adobe portable document (pdf)
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
We present new sound and complete axiomatizations of type equality and subtype inequality for a first-order type language with regular recursive types. The rules are motivated by coinductive characterizations of type containment and type equality via simulation and bisimulation, respectively. The main novelty of the axiomatization is the fixpoint rule, a finitary coinduction principle. The new axiomatizations give rise to a natural operational interpretation of proofs as coercions and to efficient algorithms for constructing explicit coercions efficiently, not only deciding type equality and type containment. More generally, we show how adding the fixpoint rule makes it possible to define inductively a a set coinductively defined as the kernel (greatest fixed point) of an inference system
[ Rectype ] [ Coinduction ] [ Coinduction ]
@article{brhe98,
Author = {Brandt, Michael and Henglein, Fritz},
Title = {Coinductive axiomatization of recursive type equality and subtyping},
Journal = {Fundamenta Informaticae},
Volume = {33},
Number = {4},
Pages = {309--338},
Year = {1998}
}
Get EndNote Reference (.ref)