On the Behavioral Inheritance of State-Based Objects
====================================================

We consider the inheritance of state-based behavior in object-oriented
analysis and design, as it arises, for example, in specifying behavior
in the UML using statecharts.  We concentrate on behavioral conformity
and the resulting substitutability of classes, whereby the inheritance
mechanism is to retain original behaviors.  There are many deep and
unresolved questions around this issue, which cannot be addressed
without a clear and rigorous picture of what exactly is meant by
behavioral conformity, and how computationally complex it is to
detect.  We first define a basic propositional-level computational
model for object-oriented designs, and then define substitutability
and inheritance in the linear and branching paradigms. We relate these
to trace containment and Milner's notion of simulation and deduce the
complexity of some of the relevant algorithmic problems.  The paper
thus sets the stage for further research on behavioral inheritance.