<p>I know almost nothing about Petri nets, so watch out for any mistakes.  The terminology in this answer follows <a href="http://en.wikipedia.org/wiki/Petri_net#Syntax" rel="nofollow">Wikipedia</a>.</p>

<p><strong>Theorem</strong>.  There is no Petri net with two distinguished source transitions S<sub>1</sub> and S<sub>2</sub> and one distinguished sink transition T such that if S<sub>1</sub> fires <i>a</i> times and S<sub>2</sub> fires <i>b</i> times, then T fires max{<i>a</i>,<i>b</i>} times eventually but T cannot fire more than max{<i>a</i>,<i>b</i>} times.</p>

<p><strong>Proof</strong>.  Suppose that there is such a Petri net, and let <i>M</i><sub>0</sub> be the initial marking.  Let <i>n</i> be the number of places in this Petri net.  A marking can be viewed as an element in ℕ<sup><i>n</i></sup>, where ℕ={0,1,2.…}.</p>

<p>Define markings <i>M</i><sub>1</sub>, <i>M</i><sub>2</sub>, … recursively as follows.  Starting with <i>M</i><sub><i>a</i></sub> (<i>a</i>=0,1,…), let S<sub>1</sub> fire once, and wait for T to fire.  Let <i>M</i><sub><i>a</i>+1</sub> be the marking after T fires.</p>

<p>By <a href="http://en.wikipedia.org/wiki/Well-quasi-ordering#Examples" rel="nofollow">Dickson’s lemma</a>, there exist indices <i>i</i>&lt;<i>j</i> such that <i>M</i><sub><i>i</i></sub>≤<i>M</i><sub><i>j</i></sub>.  Consider the following scenario.  Starting with <i>M</i><sub><i>i</i></sub>, let S<sub>2</sub> fire <i>i</i>+1 times.  Counting from the beginning, S<sub>1</sub>, S<sub>2</sub> and T have fired <i>i</i> times, <i>i</i>+1 times and <i>i</i> times, respectively.  Therefore, from this situation, T will eventually fire.  Now consider another scenario.  Starting with <i>M</i><sub><i>j</i></sub>, let S<sub>2</sub> fire <i>i</i>+1 times.  Then there exists a firing sequence which leads to T firing because <i>M</i><sub><i>i</i></sub>≤<i>M</i><sub><i>j</i></sub> (and the Petri net does not have inhibitor arcs), but this contradicts the assumption because counting from the beginning, S<sub>1</sub>, S<sub>2</sub> and T have fired <i>j</i> times, <i>i</i>+1 times and <i>j</i>+1 times, respectively, and <i>j</i>+1&gt;max{<i>j</i>, <i>i</i>+1}.  <strong>QED</strong>.</p>

<p><em>Edit</em>: The proof in revision 1 contained an error, which was pointed out by mweerden in a comment.  Now it is fixed.  Thanks, mweerden!</p>

CC BY-SA 2.5
2010-09-20T13:46:11.843Z
In fact, I suspect that a stronger statement may hold: “No Petri net computes (in the stated sense) the maximum of two nonnegative integers, even in the cases where both inputs are at most 2.”  If this holds, a proof will probably be simpler (in particular, we will not probably need Dickson’s lemma).  It is easy to construct a Petri net which computes the maximum of two nonnegative integers at most 1.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T15:12:19.320Z
Regarding the (nice) proof: "Then T will eventually fire" should probably be something like "Then there should be a firing sequence that leads to T firing." (The extra tokens might enable other transitions that break the covering of Mi.)
mweerden
CC BY-SA 2.5
2010-09-20T15:19:38.437Z
Regarding the stronger statement: I don't think that's the case. If you limit the inputs to some finite k, you can always use 2k+1 places to precisely indicate the difference between the two. (And 2(2k+1) transitions for the mutations when new tokens arrive.)
mweerden
CC BY-SA 2.5
2010-09-20T16:05:00.533Z
@mweerden: Fixed, thanks!  I was afraid that I might confuse “eventually fires” and other related notions, but I could not catch it before I read your comment.  Also, thank you for the comment about the stronger statement; your comment indeed suggests that it may be possible to compute the maximum of two _bounded_ nonnegative integers.  However, I still cannot see how to convert the “difference” Petri net to a “maximum” Petri net, which leaves slight hope for the stronger statement (unless I am missing something).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T17:05:45.733Z
Sorry, I missed that the boundedness was only a specific instance. Without it I don't see how I should interpret the statement such that your proof doesn't generalise to any Petri net. Can't you always "hang" it into the setting of the original question to find an input for which it breaks? W.r.t. the "difference" PN -> "maximum" PN, the difference is an integer (i.e. a-b and not |a-b|) and whenever you go from a difference of i to i-1 for i<=0 or from i to i+1 for i>=0, you add a token to the output (as it implies that the previous maximum input was increased).
mweerden
CC BY-SA 2.5
2010-09-20T19:12:02.577Z
@mweerden: Your original interpretation was correct.  When I wrote “compute the maximum of two bounded nonnegative integers,” I really meant to compute the maximum of two nonnegative integers for the cases where both integers are at most _k_ (without specifying the value of _k_).  And thank you for further explanation about what I was missing.  The construction which you stated indeed disproves my stronger statement in the first comment (and any variants where the constant 2 is replaced by any other constant).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T04:13:44.967Z
2010-09-20T20:04:48.847Z
2010-09-20T20:04:48.847Z
Tsuyoshi Ito
<p>Creating a petri-net that models the minimum function is quite simple:</p>

<pre><code> -----     -----
   |         |
   |         |
   O         O
   |         |
   v         v
  -------------
</code></pre>

<p>If <code>a</code> tokens arrive via source 1 and <code>b</code> tokens arrive via source 2, <code>min(a, b)</code> tokens will eventually end up in the sink.</p>

<p>Now I would like to model the <em>maximum</em> function. I found a solution, but it requires the use of inhibitor arcs. <strong>Question</strong>: Is is possible to model the maximum function without the use of inhibitor arcs?</p>

CC BY-SA 2.5
2010-09-16T21:57:39.240Z
Thinking about this may disturb my sleep. I cannot see how it can be done without inhibitor arcs, which is proof of nothing.
Dave Clarke
CC BY-SA 2.5
2010-09-16T23:41:19.257Z
What is an inhibitor arc ?
Suresh Venkat
CC BY-SA 2.5
2010-09-17T06:43:26.053Z
@Suresh: An inhibitor arc from place A to transition T means that T can only fire if A is empty. It can be used to model negations and makes the formalism Turing-complete.
Heinzi
<dc.distributed-comp><formal-modeling><petri-nets>
Is it possible to model maximization in a petri net without using inhibitor arcs?
Heinzi
# Is it possible to model maximization in a petri net without using inhibitor arcs?

(Asked by: username_0 on 2010-09-16)

Creating a petri-net that models the minimum function is quite simple:
 -----     -----
   |         |
   |         |
   O         O
   |         |
   v         v
  -------------

If a tokens arrive via source 1 and b tokens arrive via source 2, min(a, b) tokens will eventually end up in the sink.
Now I would like to model the maximum function. I found a solution, but it requires the use of inhibitor arcs. Question: Is is possible to model the maximum function without the use of inhibitor arcs?

**Tags:** dc.distributed-comp, formal-modeling, petri-nets

> **Comments:**
> **username_1**: Thinking about this may disturb my sleep. I cannot see how it can be done without inhibitor arcs, which is proof of nothing.  
> **username_2**: What is an inhibitor arc ?  
> **username_0**: @Suresh: An inhibitor arc from place A to transition T means that T can only fire if A is empty. It can be used to model negations and makes the formalism Turing-complete.  

---

## 1 answers

### Answer by username_3 on 2010-09-20. Score: 6 | Accepted answer

I know almost nothing about Petri nets, so watch out for any mistakes. The terminology in this answer follows [Wikipedia](http://en.wikipedia.org/wiki/Petri_net#Syntax).

**Theorem**. There is no Petri net with two distinguished source transitions S1 and S2 and one distinguished sink transition T such that if S1 fires *a* times and S2 fires *b* times, then T fires max{*a*,*b*} times eventually but T cannot fire more than max{*a*,*b*} times.

**Proof**. Suppose that there is such a Petri net, and let *M*0 be the initial marking. Let *n* be the number of places in this Petri net. A marking can be viewed as an element in ℕ*n*, where ℕ={0,1,2.…}.

Define markings *M*1, *M*2, … recursively as follows. Starting with *M**a* (*a*=0,1,…), let S1 fire once, and wait for T to fire. Let *M**a*+1 be the marking after T fires.

By [Dickson’s lemma](http://en.wikipedia.org/wiki/Well-quasi-ordering#Examples), there exist indices *i*<*j* such that *M**i*≤*M**j*. Consider the following scenario. Starting with *M**i*, let S2 fire *i*+1 times. Counting from the beginning, S1, S2 and T have fired *i* times, *i*+1 times and *i* times, respectively. Therefore, from this situation, T will eventually fire. Now consider another scenario. Starting with *M**j*, let S2 fire *i*+1 times. Then there exists a firing sequence which leads to T firing because *M**i*≤*M**j* (and the Petri net does not have inhibitor arcs), but this contradicts the assumption because counting from the beginning, S1, S2 and T have fired *j* times, *i*+1 times and *j*+1 times, respectively, and *j*+1>max{*j*, *i*+1}. **QED**.

*Edit*: The proof in revision 1 contained an error, which was pointed out by username_4 in a comment. Now it is fixed. Thanks, username_4!

> **Comments:**
> **username_3**: In fact, I suspect that a stronger statement may hold: “No Petri net computes (in the stated sense) the maximum of two nonnegative integers, even in the cases where both inputs are at most 2.”  If this holds, a proof will probably be simpler (in particular, we will not probably need Dickson’s lemma).  It is easy to construct a Petri net which computes the maximum of two nonnegative integers at most 1.  
> **username_4**: Regarding the (nice) proof: "Then T will eventually fire" should probably be something like "Then there should be a firing sequence that leads to T firing." (The extra tokens might enable other transitions that break the covering of Mi.)  
> **username_4**: Regarding the stronger statement: I don't think that's the case. If you limit the inputs to some finite k, you can always use 2k+1 places to precisely indicate the difference between the two. (And 2(2k+1) transitions for the mutations when new tokens arrive.)  
> **username_3**: @username_4: Fixed, thanks!  I was afraid that I might confuse “eventually fires” and other related notions, but I could not catch it before I read your comment.  Also, thank you for the comment about the stronger statement; your comment indeed suggests that it may be possible to compute the maximum of two _bounded_ nonnegative integers.  However, I still cannot see how to convert the “difference” Petri net to a “maximum” Petri net, which leaves slight hope for the stronger statement (unless I am missing something).  
> **username_4**: Sorry, I missed that the boundedness was only a specific instance. Without it I don't see how I should interpret the statement such that your proof doesn't generalise to any Petri net. Can't you always "hang" it into the setting of the original question to find an input for which it breaks? W.r.t. the "difference" PN -> "maximum" PN, the difference is an integer (i.e. a-b and not |a-b|) and whenever you go from a difference of i to i-1 for i<=0 or from i to i+1 for i>=0, you add a token to the output (as it implies that the previous maximum input was increased).  
> **username_3**: @username_4: Your original interpretation was correct.  When I wrote “compute the maximum of two bounded nonnegative integers,” I really meant to compute the maximum of two nonnegative integers for the cases where both integers are at most _k_ (without specifying the value of _k_).  And thank you for further explanation about what I was missing.  The construction which you stated indeed disproves my stronger statement in the first comment (and any variants where the constant 2 is replaced by any other constant).  

---

