An Exact Algebraic Characterization of Behavioral Subtyping

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.

Abstract

An Exact Algebraic Characterization of Behavioral Subtyping
by
Gary T. Leavens and Don Pigozzi
Abstract
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.


Subjects:
All uncategorized technical reports


ID code:
00000133
Deposited by:
Staff Account on 26 November 1996





Contact site administrator at: ssg@cs.iastate.edu