DeMO (Discrete Event Modeling Ontology)

DeMO is an ontology for discrete-event modeling (system dynamics for discrete systems). Here discrete-event system (DES) is understood as an event-driven system with discrete states.

As a first step we start by defining a taxonomy of discrete-event modeling formalisms based on their theoretical modeling power. We consider Generalized Semi-Markov Process models and Generalized Stochastic Petri Nets to be two roots of the taxonomy (highest modeling power). Other modeling formalisms are added by placing restrictions on higher formalisms (e.g. timed automata is a stochastic timed automata with a deterministic clock structure, etc).

The result is a simple hierarchical structure where objects are related through “is-a-subclass-off” (parent/child) relation.

This kind of taxonomy with corresponding links on the Web is easily browsed by humans and may serve as a good reference. However we can go further with ontologies. We can put more complex and meaningful knowledge in the ontology by using stronger semantic connections in the DES models. Not only that – we can try to make the ontology readable by machines.

OWL (Web Ontology Language) uses formal semantics to facilitate machine readability of Web contents. The language defines classes, their properties, relationships between classes (as object properties), and class instances (individuals). We used Protégé OWL plug-in (ontology building toolset) to create a discrete-event system modeling knowledge base (DeMO ontology). The resulting .owl file can be viewed in Protégé with OWL plug-in installed by means of “Import” command.

Let’s take a closer look at the DeMO ontology. It has two main classes: Model and ModelElement. Since the scope of this ontology was considered to be only DES models, the name Model is used for the sake of simplicity. In a larger ontology that spans beyond just discrete-event systems’ modeling it has to be substituted by DiscreteEventModel (or something of the sort) with the term Model to be reserved for a more general concept.

Class ModelElement as obvious from the name describes relevant model elements and contains three subclasses:

· ModelPrimitive,

· ModelBuildingBlock,

· ModelMechanism,

ModelPrimitive describes most basic, fundamental concepts of the model each of which is placed in a separate class. In the case of DES these are: State, Event, Transition, EventClock, Place (for Petri Net models), and TimeValue.

Subclasses of ModelBuildingBlock are the building blocks of the Model (each model has a “has-a” relation with them). Building blocks themselves are defined in terms of subclasses of ModelPrimitive (mostly as a “set-of”). For example StateSpace is defined as a “set-of” State, ClockStructure as a “set-of” Clock etc.

ModelMechanism contains subclasses that specify different mechanisms (rules of engagement) adopted by a particular model: EventScheduling mechanism, TransitionTriggering mechanism, etc. TimingSpecification for example explains the meaning behind the event clock sequence, and ClockSetting describes how the event clocks in a clock structure are set and itself has two subclasses StochasticClockSetting and DeterministicClockSetting.

At present we haven’t defined model mechanisms in further detail. In general at the lowest level of granularity of the knowledge base classes turn into instances. In our case we create instances of model mechanisms with names that may mean something to human observer but have no machine readable semantic meaning. We decided to stop at this level just for the sake of simplicity. One can easily imagine that a number of different subclasses and concepts can be created only to describe these mechanisms in further detail. Usually the depth (level of granularity) of an ontology is determined by the proposed application. If one considers the use of the DeMO ontology by simulating programs than clearly further details in model mechanism descriptions is necessary.

As mentioned above each of these classes has several properties that either serve to define the instances of the class (datatype properties) or the relationships with other classes. Here is a snapshot of the small part of the graphical representation of DeMO.

(Click here for pic1.eps file)

Figure 1 Graphical representation of the part of the DeMO ontology. Here Model Element classes and there relationships are depicted. [Created using ezOWL plug-in.]

Class Model contains the DES modeling formalisms’ taxonomy described above, but now the classes are defined using formal semantics, in particular by putting restrictions on model properties. For example GSMP (Generalized Semi-Markov Process model) is defined as Model with the following restrictions:

· The clock structure is stochastic,

· The transition function is probabilistic,

· Transitions are triggered by Multiple_Events_Triggering mechanism,

· Transitions are enabled through Event_Enabling mechanism (which suppose to mean that transitions are enabled together with triggering events),

· And events are scheduled through some Automata_Scheduling mechanism.

Here’s another snapshot of the part of the ontology:

Click here for pic2.eps file

Figure 2 Part of the DeMO ontology with GSMP class. [Created using ezOWL plug-in. ]

The ontology is not fully populated (not all classes have instances). As was mentioned above the decision on where to put instances is application specific. In the case of Model classes the lowest level envisioned is when each instance represents a particular model with defined state space, event set, transition function, clock structure etc. This model instances are “prepared for execution”. But one can stop at a higher level, for example by turning the lower level model classes into instances. Such ontology may prove to be very useful, especially combined with other ontologies and inference tools.