<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Time and Concurrency - Three Approaches for Intertwining Time and Petri Nets</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Louchka Popova-Zeugmann</string-name>
          <email>popova@informatik.hu-berlin.de</email>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Department of Computer Science Humboldt University Berlin</institution>
          ,
          <country country="DE">Germany</country>
        </aff>
      </contrib-group>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>-</title>
      <p>Time and Petri nets - do they not contradict each other? While time determines the
occurrences of events in a system, classic Petri nets consider their causal relationships
and represent events as a concurrent system. At first, these two appear to be at odds
with each other, but taking a closer look at how time and causality are intertwined, one
realizes that time actually enriches Petri nets. There are many possible ways in which
time and Petri nets interact, this talk will take a short look at three time-dependent Petri
nets: Time Petri nets, Timed Petri nets, and Petri nets with time-windows. For the first
nets that we will take a look at, Time Petri nets, enabled transitions may fire only during
specified time intervals. The transitions must fire the latest at the end of their intervals
if they are still enabled then. At any given moment only one transition may fire. This
firing does not take time. For the second class of nets, Timed Petri nets, a maximal
set of just-enabled transitions fires, and the firing of each transition takes a specific
amount of time. The third class of nets, Petri nets with time-windows, portrays time
as a minimum and maximum retention for tokens on places. In these nets tokens can
be used for firing only during their minimum and maximum retention. At the end of
the maximum retention time for a token its time is reset to zero if it was not used for
firing. The next period of its retention time on this place then restarts. This repetition
can continue indefinitely. For Time Petri nets, we provide an algorithm which proves
the behavioral equivalence of a net where time is designed once with real and once
with natural numbers. One can also say that the dense semantics of Time Petri nets
can be replaced with discrete semantics. For Timed Petri nets, we introduce two
timedependent state equations. These provide a sufficient condition for the non-reachability
of states. Last but not least, we prove that Petri nets with time-windows have the ability
to realize every transition sequence fired in the net omitting time restrictions. Despite
the first experience that time has no influence on the behavior of such nets, we verify
that the time can change the liveness behavior of Petri nets with time-windows. We
choose these three classes of time-dependent Petri nets to show that time alone does
not change the power of a Petri net. In fact, time can or cannot be used to force firing.
For Time Petri nets and Timed Petri nets we can say that they are Turing-powerful, and
thus more powerful than classic Petri nets. In contrast to these two nets, Petri nets with
time-windows have no compulsion to fire. Their expressiveness power is less than that
of Turing-machines.</p>
    </sec>
  </body>
  <back>
    <ref-list />
  </back>
</article>