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.
Our goal is to investigate the notion of behavioral conformity and the resulting substitutability of classes, whereby the inheritance mechanism is to retain original behaviors. This is a central issue of crucial importance to the modeling, design and verification of object-oriented systems. There are many deep and unresolved questions around inheritance, 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 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.'