Browse Prior Art Database

Algorithm to Optimize State Transition Data Structures Associated with Supertype Events

IP.com Disclosure Number: IPCOM000116833D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 123K

Publishing Venue

IBM

Related People

Chen, C: AUTHOR [+3]

Abstract

This article describes an algorithm to optimize state transition data structures associated with supertype events. In an object-oriented system, objects can be organized into a hierarchy of classes or types, with subordinate types called "subtypes" inheriting attributes from their supertypes. The ability to receive certain kinds of messages (events) is a capability that subtypes inherit from their supertypes.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 37% of the total text.

Algorithm to Optimize State Transition Data Structures Associated
with Supertype Events

      This article describes an algorithm to optimize state
transition data structures associated with supertype events.  In an
object-oriented system, objects can be organized into a hierarchy of
classes or types, with subordinate types called "subtypes" inheriting
attributes from their supertypes.  The ability to receive certain
kinds of messages (events) is a capability that subtypes inherit from
their supertypes.

      The behavior of objects within each class or type can be
represented by a finite state machine (state model).  One
representation of a state model is the two-dimensional matrix, with
each row identifying a separate state, and each column identifying a
separate event which can cause a state-transition.  The contents of
each cell in such a matrix are used to identify the destination state
of the transition from the state identified by its row in the matrix.

      Due to the inheritance of the ability to receive supertype
events by subtypes, the state models of subtypes must allow for
supertype events to be received.  In the two-dimensional matrix
representation of state models, this means that there must be columns
in the matrix to accommodate supertype events, as well as columns to
accommodate events which are unique to the subtype, that is, events
which are not inherited.

      To optimize the data structures associated with the state
models in an object-oriented system, the two-dimensional matrices
representing each state model need to be synchronized for supertype
events.  What this means is that the ordinal position of columns for
events in the two-dimensional matrices must follow certain criteria.
This ordinal column position for a given event is called the
"Relative Event Number."
  1.  All supertype events must be represented by a column in the
       matrix for the subtypes.  If subtypes have further lower
subtypes
       (such as grandchildren, great-grandchildren, etc., types) then
       those subtypes must also accommodate a column in their matrix
for
       the supertype events.
  2.  The Relative Event Number for any particular event within a
       matrix for any one type must be the same within all matrixes
that
       contain a column for that same event.
  3.  The Relative Event Number for events within any matrix must
have
       a sequence which correlates the ancestry in the supertype
       hierarchy such that more superior supertype events have lower
       ordinal positions than less superior supertype events.  The
lower
       subtypes events have higher ordinal positions within the
       matrixes.  The events which are unique to the lowest
subordinate
       type in a hierarchy will have the highest ordinal positions of
       columns for events in the matrixes.

      Since inheritance proceeds f...