We
want to compare two formalisms based on their modeling power. We understand the modeling power in the
following way - two formalisms have equivalent modeling power if they can model
the same class of (discrete-event) systems.
Consider
the following connections between Petri Nets and State Automata. It is easy to
show that given any finite state automaton it can be directly turned into a
Petri Net by simple replacing the events of the automaton with the transitions
of the Petri Net with one input and one output. On the other hand for any Petri
Net we can construct a reachability graph and the
resulting graph will itself be a state automaton, since we allow the state set
of an automaton to be countably infinite. ( ? It is
still unclear though how to go from an arbitrary state automaton with infinite
number of states to a Petri Net…?).
Another
complication arises from the fact that these mappings only deal with untimed
deterministic models. For formalisms in consideration we also need to consider
how to map stochastic clock structures and probabilistic transitions from Petri
Nets to State Automata and back. (? This may be not trivial…?)
1. C. G. Cassandras, S. Lafortune, Introduction to Discrete Event Systems, Kluwer, 1999.