Discrete-Event Modeling Ontology (DeMO):
Model Elements
DeMO is an ontology for discrete-event modeling (DEM) (system dynamics for discrete-event systems (DES)). The models in the ontology focus on how
state evolves over time. The state is typically discrete (finite or countable), while time may be continuous (uncountable), although the number of state
changes (events) must be discrete. We also focus on stochastic models, although deterministic models are considered as a special case. It is hoped that
the DeMO ontology will be useful to researcher and practitioners of modeling and simulation. Such an ontology could also find application in locating
modeling and simulation software, particular modeling applications and modeling components as well as facilitating meta-modeling and multi-modeling. This
page represents preliminary information being used to create the DeMO ontology.
Warning - Rough Draft
Nomenclature
Basic Sets
In discrete-event models, the state of a model changes
at discrete points in time at which events occur, so
all such models require the following three basic sets:
State Space (S), Event Set (E) and Time Set (T).
Together they form the S, E, T sets.
-
State -
A model changes over time from
state to state.
Its current state at a particular time is quantified
by the values of a collection of indicators.
Indicators record various properties of the model.
State s(t) in S gives the values of these
indicators at time t.
-
Event -
An event
characterizes a type of event instance that may occur.
An event instance occurs instantaneously at a particular time and
may cause a state change and/or future events.
Event e in E is enabled at time t1
and fires at time t2.
The difference between these times is referred to as the
event lifetime.
The combination of the event and its firing time
may be viewed as an event occurrence (e, t).
-
Time -
A nonnegative number representing the passage of
time.
Time t in T is integer-valued for discrete-time models
and real-valued for continuous time models
(vector-valued time is also a possibility).
Initialization Function
Given the three basic sets (S, E, T),
the model must be initialized to reflect appropriate
starting conditions. In general, this can be done
with an initialization function b,
which will assign a value to the state at the beginning
of time.
Driving Functions
Given the three basic sets and the initialization function
(S, E, T, b)
for a model, its dynamics (how it evolves over time)
can be specified by two driving functions:
one determining when events may occur
and the other determining what happens when an event occurs.
These are the Clock-Function (c) and
the Transition-Function (d), respectively.
-
Clock-Function -
When the model enters a given state, the clock
function will determine the future events that
may occur, a set of (e, t) pairs.
For automata models, all future events are
generated upon entering the start state and
may be viewed as input.
For Markov models, non-absorbing states
will use the clock function to generate
future events, which provide the means for
leaving that state.
An event is said the be enabled once generated
and if it is not cancelled, will fire after a
period of time.
Clock-Function c : S x E -> T
-
Transition-Function -
A state change that is caused by one events.
(In some generalized models a transition may be caused by
muliple simultaneous events.)
For the one event case, the occurrence of event e
at time t causes a transition from the old state s(t-)
to a state new s(t). The type of the event as well as
the value of the old state together determine the new state.
Transition-Function d : S x E -> S
Note, these definitions assume a time-homogeneous model
where the laws governing the dynamics do not change over time;
otherwise, time would need to be added to the domain for
these functions.
Embellishments
Given the basic sets and functions
(S, E, T, b, c, d)
for a given model,
one could visualize the evolution of the model
by imagining
one or more tokens moving around in the model.
For Markov and automata models, it is natural to
use one token to represent the current state.
For other types of models (e.g., Petri Nets),
multiple tokens may be required.
In these types of models, a token resides
at a given place until it is involved in a transition.
Finally, tokens can be differentiated by using
colors.
-
Token -
A token (or entity or mark) represents a thing of interest within a model
that exists for a period of time (its lifetime).
Typically, a token/entity moves through the model.
Token m at any time t is at a particular place and may
have its own properties.
Note, if tokens are indistinguishable and the system is Markovian,
then the state s(t) can be determined by counting the number of tokens at
each place.
-
Place -
A place is a location within a positional
space
(e.g., a metric space or
topological space)
indicating where a token is.
Place p is a location within the model
(e.g., logically at a node in a graph
or physically in an n-dimensional coordinate system).
-
Color -
The color (or hue) of a token is used to distinguish different types of tokens.
Color h(m) indicates the type/classification of token m.
Composites
-
Activity
- An activity is initiated by an event e1 at time t1
and terminated by an associated event e2 at time t2
with the duration being t2 - t1, (e1, e2, t2 - t1).
-
Process
- A process gives the value of the state over the model's lifetime T,
{(t, s(t)) | t in T}.
The process may be classified as either deterministic or stochastic.
-
Environment
- that which is outside the boundary of the model.
-
Input
- The events that are produced by the environment,
exogenous events.
In automata, the event set E may be called the
alphabet and the input string will correspond to
the result of applying the clock function to the initial state.
(The other events are referred to as endogenous events.)
-
Output Function
- An output function is not an inherent part of the model,
but rather an interpretation or view of the model's execution.
A result value (in the result set R) may be produced
when an event occurs based upon the current state and the event
(Mealy machine).
If the output function is solely determined by the state,
it is referred to as a Moore machine.
Output Function o : S x E -> R
Categories
Dynamicity
-
Static - a model without time or the projection of a model onto
a particular time.
-
Dynamic - otherwise.
-
Time Homogeneous - the driving functions are independent of time.
-
Time Inhomogeneous - otherwise.
Cardinality
-
k-Bounded - there exists k such that for all
sets s, | s | < k.
-
Finite - for all sets s, there exists a k such
that | s | < k.
-
Countable/Discrete - for all sets s, there exists a injection from its elements
to the set of integers.
Note: Countable subsumes Finite which subsumes Bounded.
-
Uncountable/Continuous - otherwise.
Determinancy
-
Deterministic - s(t) in S.
-
Nondeterministic - s(t) in PowerSet(S).
-
Stochastic -
Nondeterminism with a tendency restriction specified
with a probability measure P such that
P(s(t) = k) = [0, 1] for all k in S
Openness
-
Closed - a model having no input or output
-
Open - otherwise
Topology
-
Directed Graph - G(N, E) where N is a set of nodes and
E is a set of edges (ordered pairs of nodes).
-
Directed Hypergraph
Solutions
-
Transient Solution - compute the system trajectory.
In the deterministic case this will be an ordinary function.
In the stochastics case it will be a random function.
If the dynamics are complicated, mathematical solutions
may be intractable, in which case the function may be
estimated by generating sample paths/traces (subject of
simulation).
-
Terminal Solution - compute the limit of the trajectory as
time goes to infinity or to the system stop time.
-
Steady-State Solution - a special case of terminal in which
the system has reached equilibrium before termination.
If equilibrium is reached quickly enough, simulation can be used
as an estimation procedure.
-
Input Characterization - what input functions will lead to
acceptable terminal solutions.
The set of all such input functions or streams is referred to
as a language.
-
Optimization -
-
Structural Analysis -