| Coinductive Axiomatization of Recursive Type Equality and Subtyping (1998) | |||||||||||||||||
Abstract | |||||||||||||||||
| . 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 (or coinduction principle). It states that from A; P ` P one may deduce A ` P , where P is either a type equality ø = ø 0 or type containment ø ø 0 and the proof of the premise must be contractive in a sense we define in this paper. In particular, a proof of A; P ` P using the assumption axiom is not contractive. The fixpoint rule embodies a finitary coinduction principle and thus allows us to capture a coinductive relation in the fundamentally inductive framework of inference systems. The new axiomatizations are more concise than previous axiomatizations, particularly so for type containment since no separate axiomatization of t... | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||