archives

An Exact Algebraic Characterization of Behavioral Subtyping


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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.

Full text available as:Postscript
Adobe PDF

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