7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Thinking about this may disturb my sleep. I cannot see how it can be done without inhibitor arcs, which is proof of nothing. $\endgroup$
    – Dave Clarke
    Commented Sep 16, 2010 at 21:57
  • $\begingroup$ What is an inhibitor arc ? $\endgroup$
    – Suresh Venkat
    Commented Sep 16, 2010 at 23:41
  • $\begingroup$ @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. $\endgroup$
    – Heinzi
    Commented Sep 17, 2010 at 6:43

1 Answer 1

Reset to default
6
$\begingroup$

I know almost nothing about Petri nets, so watch out for any mistakes. The terminology in this answer follows Wikipedia.

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 M0 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 M1, M2, … recursively as follows. Starting with Ma (a=0,1,…), let S1 fire once, and wait for T to fire. Let Ma+1 be the marking after T fires.

By Dickson’s lemma, there exist indices i<j such that Mi≤Mj. Consider the following scenario. Starting with Mi, 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 Mj, let S2 fire i+1 times. Then there exists a firing sequence which leads to T firing because Mi≤Mj (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 mweerden in a comment. Now it is fixed. Thanks, mweerden!

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 20, 2010 at 13:46
  • 3
    $\begingroup$ 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.) $\endgroup$
    – mweerden
    Commented Sep 20, 2010 at 15:12
  • 1
    $\begingroup$ 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.) $\endgroup$
    – mweerden
    Commented Sep 20, 2010 at 15:19
  • $\begingroup$ @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). $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 20, 2010 at 16:05
  • 1
    $\begingroup$ 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). $\endgroup$
    – mweerden
    Commented Sep 20, 2010 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.