Leavens, Gary T. and Pigozzi, Don (1996) An Exact Algebraic Characterization of Behavioral Subtyping. Technical Report TR96-15, Department of Computer Science, Iowa State University.
An Exact Algebraic Characterization of Behavioral Subtyping
Gary T. Leavens and Don Pigozzi
A model theory for correct behavioral subtyping for abstract data
types (with immutable objects) is developed within the framework of
the behavior-realization adjunction. To allow for incomplete
specifications, proofs of correct behavioral subtyping are based on
comparison to one of several paradigmatic models. For specifications
that are not term-generated, these results are the first complete
algebraic characterizations of behavioral subtyping.
Keywords: behavioral subtype, subtyping, behavior, realization,
observable equivalence, simulation, abstract data type.
1994 CR Categories:
D.3.3 [Programming Languages]
Language Constructs --- Abstract data types;
F.3.2 [Logics and Meanings of Programs]
Semantics of Programming Languages --- algebraic approaches to semantics;
F.3.2 [Mathematical Logic and Formal Languages]
Mathematical Logic --- model theory.
1991 Mathematics Subject Classification.
Primary: 68Q65 Secondary: 68N05, 68N15, 68Q60.
Contact site administrator at: firstname.lastname@example.org