Talk:Petri net/Archive 1

Archive 1

Question about software list

Could it be too difficult to separate free or GPL software from commercial packages in the list? from mtodorov3_69@yahoo.com

I would take that as a goal for the proposed new separate tools article (see other thread). Maybe not in the first step. I think we'll need to identify tools first by supplying external links. So the first step would be to have just one list. Later, that list could be organised like in List of UML tools. — Adrian | Talk 17:37, 12 November 2005 (UTC)

Regular editor of this article

Hi everyone! It seems like I am the regular editor of this article. I would like to have many volunteers, but there doesn't seem to be many around. If you would like to help, your help is welcome. Make big changes if you whish! Also, if you have any problems, you can contact me at my talk page! Msoos 20:04, 12 April 2006 (UTC)

I saw your request on Wikipedia:Pages needing attention. I found the article very readable, so well done! The only quibble I have is the handling of the examples. It took me quite some time to locate example (a). I also think that the other example should be separated more clearly from the rest of the text. Perhaps you can explain one of the examples in words, as the definitions may be difficult to understand in one go. On the other hand, the animation in the first picture is great; for me, it explained what Petri nets are (though I might have seen them before). -- Jitse Niesen (talk) 04:06, 3 June 2006 (UTC)

Removed boundedness as an inherent property

Boundedness was removed as an inherent property for the reasons:

• I have never seen a textbook that described Petri nets with the inherent boundedness as an original property
• It restricts the power of petri nets amazingly
• It can be (and should be) introduced later
• It can be mimicked with a place-transformation and a restricted starting state
• It was requested by some people, and I have been personally asked by several to change it.
• People who read this article want the standard definition, not some obscure one.

Hope no one objects (I am pretty sure none will) Msoos 12:55, 3 December 2006 (UTC)

Removal of section on Subsequent models

I am proposing to remove the section on subsequent models. The category system provides a list of related models of concurrency. The present section (and the word "subsequent") seems to suggest that other models are somehow better than petri nets. This is surely a subjective claim that really has no place on the main petri net page. I'll wait a few days for discussion before deleting. Sam Staton 12:06, 27 July 2007 (UTC)

I have cut down this section now, as proposed. If someone objects, I'm happy to discuss. I am well aware that there are other models of concurrency around, that don't have wikipedia entries. Sam Staton 19:07, 30 August 2007 (UTC)

determinism

Whether or not a petri net is deterministic is dependant on its rule definition. you can define a net with or without timing, with or without capacity constraints etc. e.g. when you define net rules so that a transition multiplies tokens and there is no time and all firing thats possible happens at once you can have a fully deterministic net, wich is btw. much more easy to analyze.

Yes, deterministic nets are way easier to analyse - they are however not terrible interesting. Petri nets are usually used to analyse systems with some amount of concurrency which leads to "nondeterminism" in the way of their casual ordering. You don't need any "fancy" constructs to get there. This is generally why you don't analyse the net itself but its state space. Tveon 06:58, 6 November 2007 (UTC)

Fixing reference

rp, I'm fixing to put the reference in now. About your comment on place capacities ... that is fundamental to the safety property. The classical 1-safe Petri net has no place capacity annotations, which imply each place has a capacity of 1. If you wanna implement a network of finite capacity queues, each with known capacity, then you gotta have place capacities so annotated. All this said, it sure would be a good idea if Wil van der Aalst were to take a look at this Petri net article before we get too far into this thing. Just tell 'em John Sloan from Florida needs a little help. ... He'll understand. Vonkje 21:15, 9 Jun 2005 (UTC)

As far as I can see, capacities can be simulated (create an "anti-place" for each place with the reverse flow and initialized with the place's capacity). They're gone now, anyway. Rp (talk) 16:35, 10 July 2008 (UTC)

Reachability

The Reachability section redlinks to Reachability problem (and no other articles do). However, I have found Reachability to exist, and it looked like it is what the link intends to illustrate, but I'm not an expert so I can't say for sure. If you are an expert, please do replace the link if you think it is appropriate. TIA, László (talk) 14:51, 11 March 2008 (UTC)

I am not a recognized expert on Petri nets by any means, but I am familiar with the basic literature, and I concur with your interpretation of the text on reachability. All descriptions of it I have seen end up resorting to a graph-theoretic explanation. Duh, I guess. Anyway, I'll go ahead and fix the link. Mark Durst (talk) 16:04, 28 May 2008 (UTC)

It is the same thing. Rp (talk) 20:31, 10 July 2008 (UTC)

Place capacities

I've been dealing now with Petri Nets for a while now as applied to reliability engineering and have read up on them fairly extensively, and nowhere has there been mentioned that for a transition to switch, its output places must be below a certain level. Place capacities have not been mentioned either. Are you sure that these are aspects of standard PNs? Its just not something I've seen before. --El Pollo Diablo | Talk 10:23, 18 July 2005 (UTC)

Hi El Pollo Diablo,

Regarding place capacity restrictions within a formal definition of a Petri Net, please see the reference:

Jörg Desel and Gabriel Juhás, "What Is a Petri Net? -- Informal Answers for the Informed Reader", Hartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001.

Once you find this paper in Volume 2128 of Lecture Notes in Computer Science, turn to section 3 and you will notice that the formal definition appearing in this Wikipedia article was lifted directly from it. Please do me a favor and be sure that the definition I gave is the same as theirs. According to those at the most recent Advanced Course on Petri Nets in September 2003, this definition constitutes a "consensus" definition of what a Petri Net happens to be, but this is more precisely known as a place/transition net. Let me explain why I put the term "consensus" in scare quotes:

Regarding place capacities, the classical 1-safe Petri net has a number of deficiencies, one of which is an inability to represent queueing networks and other situations requiring capacity restrictions on places of capacity exceeding 1. Since Petri's dissertation, a number of extensions have addressed this. Desel and Juhás' definition inherits earlier definitions that include this extension for place capacities.

Your question concerning thresholds on output places is a consequence of transitions, arc weights, and place capacities working together. Suppose an output place has a capacity of 3, but already contains 2 tokens. Suppose the arc feeding this place has a weight of 2. The transition feeding the arc will not fire until the number of tokens decreases to a threshold of 1 or less. In other words, the available capacity of the output place needs to be sufficient to accommodate the number of tokens produced when firing the transition, otherwise the transition will block until the number of tokens falls below this threshold. This is one example of the safety condition enforced by all n-safe Petri Nets, and as you can appreciate, is a concept fundamental to Reliability Engineering.

The use of the term "Standard Petri Net" is a misnomer (hence my scare quotes for the word "consensus"). There really isn't a standard Petri Net. Instead there are classic Petri nets with extensions that have been formulated over the years due to some lack of expressiveness in the classical model. Do you know, for example, that the Classical Petri Net (ie: the one that Carl Adam Petri described in his dissertation) was not Turing expressive? In response to this, other authors included inhibitor arcs that when tokens are present on the place feeding the inhibitor arc, the transition will not fire. This extension was enough for Petri Nets to be Turing complete. From what I understand, there are about three other extensions different from this one that also realizes Turing expressiveness.

This all brings me to my request that we do major revisions to this article. It should stylistically be more along the lines of a Mathematics article (ie: layman's definition, followed by motivation and importance, formal definitions, notable results or theorems). More importantly, with a technology like this gathering so many (useful) barnicles, a history section should have several paragraphs. It should start with that flavor of Petri Net described by C.A. Petri, perhaps best done as a translation from the German Wikipedia. Follow this with a paragraph on each of the half-dozen or so notable extensions until today. The next section should describe each extension in one (reasonably short) paragraph accompanied by a formal definition, its behavioral properties, and the type of applications. Another section should describe Petri nets from an application point of view, and organized by problem domain (ie: reliability engineering, safety engineering, and workflow design and analysis). A final section on tools could be a fleshed out version of the existing tools section but confined to one sentence per tool. The result, unfortunately, is an article that will be three times its current size. This may then require some factoring although there is a movement afoot to prevent factoring, and putting everything into one big container. Vonkje 01:33, 20 July 2005 (UTC)

Well, all this is a lot of text but I still feel that place capacities do not belong in the standard definition of Petri nets.

Jörg Desel and Gabriel Juhás are definitely qualified as much as anyone to give definitions, but on the other hand, I feel that Wikipedia, being an encyclopedia, should use definitions that best describe common use of the terms they define, and although capacities are used with Petri nets quite often, I'm pretty sure only a very small minority of students will encounter them as part of the basic definition of what a Petri net is. So I feel it's best to introduce place capacities as one out of a long list of popular extensions to the basic Petri net formalism. Rp 18:30, 10 July 2006 (UTC)

Rp, hi .. sorry I did not get back with you sooner .. I must have overlooked your comment. Since Msoos had reworked a good portion of this article but kept the formal definition section intact, it might be time to rework this section, say, starting with the basic definition (ie: Petri net is a tuple C = (P, T, I, O) etc. etc. etc (see Peterson's article in ACM Computing Surveys)), then extend it with place capacities and arc weights and types (or colours). The result is a reworked Formal Definition section. Another approach might be to fold formal definitions into four of the main types of Petri net including Classical, P/T, Coloured, and High Level. This could address your concern for a much-needed gradual introduction to this topic. Vonkje 04:10, 21 August 2006 (UTC)

Yes, I would agree with this. In classical Petri nets there is no capacity, which does not mean - as you state above - that all places have capacity 1, but rather - as El Pollo states - that the capacity is unlimited. What is more, this is fundamental to the power of Petri nets: with limited capacities they become equivalent to (though possibly much more compact than) finite state machines. Rp 22:25, 28 August 2006 (UTC)

I could not agree more. In fact, it was a pain in the a** to write the article this way. I think I will rewrite it without place-capacities in the definition, and slowly introduce them. Arc weights are in fact just not drawing the arcs multiple times, so I would rather have them defined in the first moment, because they are simply differences in drawing. Msoos 16:28, 30 August 2006 (UTC)

I recently rewrote the definitions section, it is now more like that in Peterson's textbook, which I cite for that reason. Rp (talk) 12:11, 24 July 2008 (UTC)

My editions

Please read my comments. The introduction had *HUGE* mistakes, I corrected them. My teacher would have definitely flanked me in my "formal methods" exam had I said what was written there. So I corrected. In case you doubt my knowledge, please consult a book/article/professor - I am very sure of what I have written.

The timed petri nets thing -well. I wrote some stuff, not exactly the best ever (e.g. priorities are not defined - they should be, it is an extension of Petri nets, too). Edit if you wish (and you consider yourself knowlegable in the topic). Other than that... I would be interested, how many people watch this page - just drop here a note that you have read my comment, then I will know. I have a feeling that not too many ( - the introduction had too big mistakes for anyone that knows Petri nets to notice it)

Msoos 01:14, 30 December 2005 (UTC)

You might consider adding some references to back up your assertion that "...please consult a book/article/professor - I am very sure of what I have written."

Not that I am saying that you are wrong in anything you have written. But specific references make it easier for others to check your work. Not to mention that providing references is a recommended practice. --Allan McInnes (talk) 20:51, 13 April 2006 (UTC)

Well, I disagree with the intro. (At least the current version - haven't checked to what extend it has been edited during the last two years).

(High-level) Petri Nets are not a representation of any system. They are used for specification, design and analysis of discrete event systems through modeling. They are a graphical rather than a mathematical representation of the modeled system, although they are mathematically defined. It is also worth mentioning, that Petri nets are actually executable.

BTW, the above is adapted from the introduction in ISO/IEC 15909-1:2004(E) (High-level Petri nets - Part 1: Concepts, definitions and graphical notation). So it is not just something I've pulled out of my arse.

121.220.154.176 10:45, 27 October 2007 (UTC)

I completely agree with you. There are times as an editor when you just look at an article, sigh, and then walk away. And that's too often the case with the vast majority of the IT articles that I've come across. Including this one. --Malleus Fatuarum 12:38, 27 October 2007 (UTC)

I have made an attempt to improve things, but the introduction is still lacking in a major way (eg no good examples); but the rewrite is big enough that the above comments should be revised. Please do! Rp (talk) 12:11, 24 July 2008 (UTC)

Moving list of tools to a separate article

I would like to move the list of tools into a separate article and put a link to that new article into the "See also" section. I would name the new article "List of petri net tools" (see also Category:Lists of software, or List of UML tools as an example). If there are no objections, I'm going to do that. — Adrian | Talk 16:03, 12 November 2005 (UTC)

The name of the new article should better be List of Petri net tools. "Petri" is a proper noun and is capitalized. So the usual rule to use small caps for second and subsequents words in the name of an article does not apply. See naming conventions. — Adrian | Talk 17:30, 12 November 2005 (UTC)

I have just done the move as proposed. The new article is List of Petri net tools. — Adrian | Talk 21:40, 15 November 2005 (UTC)

Well, that article was deleted for lack of substance, and I don't disagree. Better re-insert the contents here. Does anyone know how to dig up the last contents of a deleted article? Rp (talk) 13:30, 28 July 2008 (UTC)

Notation

I am new to Petri nets and are having trouble with some of the notations. The definition of the transition relation in the Execution Semantics section contains the expression:

M=M"+{A(s)|(s,t) in A} and M'=M"+{W(s)|(t,s) in A}

This {A(s)|(s,t) in A} seems to signify a sort of multiset "slice" which somehow generates a multiset of places from A. Are the multiplicities for different transitions added up? Likewise, the second term seems to add to M" the multiset of places which are targets of arcs from any transitions. Could someone who knows more about these things define A(s) and W(s)?

In the section on Petri net types, expressions like |s.| and s. are frequently used. This probably means the sum over t of A(s, t). Could someone check and perhaps add an explaining sentence? —Preceding unsigned comment added by 92.227.68.109 (talk) 10:20, 25 October 2008 (UTC)

Added petri net types + graphical petri net example

I Added petri net types and an example petri net. If you don't like the picture, please replace it with a better one. I believe at least one picture is needed, after all Petri nets are popular, because they are visual! If they weren't they would be much harder to use.

Types are the standard types. Many things can be written about them, I wrote the most important things. Correct the wording/phrasing if you wish.

Msoos 20:47, 19 December 2005 (UTC)

First example (gif animation) seems wrong, because transition must get activated once the number of mark in places from incoming arcs are enough to feed the transition. I'm not sure it's wrong or right, but it should be fixed if it's wrong. —Preceding unsigned comment added by 88.2.190.210 (talk) 12:50, 23 July 2008 (UTC)

It's not wrong; I rewrote the sentence in the article that explained it since it wasn't clear to you apparently. Let me know if it's better now. Rp (talk) 12:11, 24 July 2008 (UTC)

Can you add more references for the definitions of Petri net types? The definition of free-choice Petri net in Desel and Esparza's Free-choice Petri nets is different. In fact, they did mention the principle of no conflict and no synchronization in the introduction, but then used a more general definition throughout the book: A Petri net $({\mathcal {P}},{\mathcal {T}},{\mathcal {F}})$ is free-choice if for every two places $p,q$ and every two transitions $t,u$

$(p,t)\in {\mathcal {F}},(p,u)\in {\mathcal {F}},(q,t)\in {\mathcal {F}}\Rightarrow (q,u)\in {\mathcal {F}}.$

In my opinion, this definition illustrate better the idea of "free-choiceness": if two transitions have some common input places, then either the two are enabled, or none of them is enabled.

Thachx (talk) 14:51, 2 December 2008 (UTC)

Well, I wrote that part... Dunno, I think what I wrote is clear. Maybe you could somehow integrate what you said as a sort-of "it could also be formulated as..." - but in a way that the reader doesn't get confused? If so, go ahead, and do it, I am all for expanding and clearing up this article! (PS: It's always best to fill up your user page with some info about yourself) Msoos (talk) 21:47, 7 December 2008 (UTC)

Guards

The word "guard" only appears once, when referring to "the well-formed Petri nets, where the arc and guard expressions are restricted". I eventually found here a description of guards. Are they part of normal/official petri nets? From the article now, it sounds like they are, but they are never mentioned. (I was having trouble figuring out how to do anything with petri nets until I found guards!) —Preceding unsigned comment added by 64.81.170.62 (talk) 01:14, 11 September 2007 (UTC)

Yes, guards are a part of standard (high-level) petri nets. However they are occasional referred to as "transition conditions". That is a more descriptive term, but it is way to long to be convenient. Guard is therefor normally the preferred word. The term "well-formed Petri net" is however not recognized in the Petri net community, where such nets are known as "symmetric (Petri) nets" - the "Petri" part is usually implicit. 121.220.154.176 10:27, 27 October 2007 (UTC)

So the answer is: no, they are not part of standard Petri nets, but of a certain extension, "high-level Petri nets", and other types of colored Petri nets. In such nets, tokens have values that can be used in computations and often in tests as well. Rp (talk) 12:31, 13 January 2009 (UTC)

But,,, What's it For?

In the opinion of this reader, the article is badly in need of text to support a reasonably intelligent, but otherwise uninformed and non-specialised reader make sense of the topic (Petri Nets).

To give an example - I arrived at this site after clicking a link in an article on workflow management. I came with no notion of what Petri nets are, how they apply to work flow management or any other application area, and I am leaving none the wiser.

A frequent complaint among some readers is that some articles are directed only toward a specialised audience. I don't wish to repeat this complaint, as I believe there are situations where a rigorous treatment is appropriate. Still, the writers here would be doing a service to the larger community by constantly keeping the needs of less specialised readers in mind as well.

--Philopedia 23:21, 18 October 2006 (UTC)

I agree, it's pretty darned abstract. I think the answer you're looking for might be something like: "It's like a State machine, except you can be in many states at once, which allows concurrency". I think the State Machine article is a little bit less abstract, anyway. Can somebody make a concrete example for the article? —Preceding unsigned comment added by 64.81.170.62 (talk) 01:12, 11 September 2007 (UTC)

The article still needs good examples to illustrate what Petri nets are actually good for. Please volunteer examples. I have a collection, but most were done by others, so I can only volunteer my own for copyright reasons. Rp (talk) 19:51, 25 June 2009 (UTC)

Liveness

The following statement in the section about liveness:

"Note that these are increasingly stringent requirements: $L_{j+1}$-liveness implies $L_{j}$-liveness."

seems not to be true for j=0 according to the definitions given in the article:

• $L_{0}$-live (dead), iff it can never fire, i.e. it is not in any firing sequence in $L(N,M_{0})$
• $L_{1}$-live (potentially fireable), iff it may fire, i.e. it is in some firing sequence in $L(N,M_{0})$

Indeed $L_{1}$-liveness is the exact negation of $L_{0}$-liveness, isn't it?

Or am I missing something? Matteosistisette (talk) 19:40, 18 October 2009 (UTC)

Spot on. Fixed. Rp (talk) 16:14, 21 October 2009 (UTC)

Merger proposal

Came across Event driven petri nets during new page patrol. I don't know that much about the subject, but given the short content of that article, and that it would have to depend on what is in Petri nets, it made sense to merge it into a section of Petri nets rather than leave it as a stand-alone article. Singularity42 (talk) 20:18, 15 November 2009 (UTC)

Seconded. There are thousands of articles on Petri nets, and hundreds of variants. We can't just go ahead and list each one of them that has ever been defined as a separate article. Even if a variant merits its own article, it should start out as a paragraph here. Rp (talk) 16:47, 16 November 2009 (UTC)

I am still working on the Event driven petri nets page. Ninjai 20:00, 19 November 2009 (EST)

I just came across the article in the list of articles to be wikified. I don't know enough about the subject to know if it should be merged. What I do know is that "I believe" is not appropriate for a WP article. Itsmejudith (talk) 17:45, 7 December 2009 (UTC)

I think the same can be said about Dualistic Petri nets. The writer make its seem as though they are a completely new idea, but the Petri net editor I worked on, Yasper, also supports transition markings and I'd be very surprised if it was the first to do so. Rp (talk) 15:31, 27 January 2010 (UTC)

I agree that all petri net articles be merged into the single. —Preceding unsigned comment added by 164.39.122.16 (talk) 13:59, 27 May 2010 (UTC)

Colored Petri Nets

"Colored Petri net" redirects here, but there is absolutely no information on Colored Petri Nets on this page. Given their popularity in "the modeling community" and elsewhere, shouldn't there be an article or a section somewhere? I'm probably going to write one. [ɯ:] (talk) 10:46, 28 February 2011 (UTC)

I agree. They are sufficiently popular, I think, and sufficiently different from standard P/T nets to warrant their own article - but make sure you start by finding some good references to prove their popularity. Rp (talk) 15:13, 4 March 2011 (UTC)

If your going to mention their popularity then you'll need a source, but im pretty sure you can just create the page.Millertime246 (talk) 23:02, 25 October 2011 (UTC)

Additive and Subtractive Closures Required on the Natural Numbers

Multiplicity mappings and markings should not be interpreted as mappings to the natural numbers (N). As a transition t fires, tokens are subtracted from its input places and accumulated at its output places. The monoid (N, +) is well-defined, which implies that accumulations of tokens at the output places are also well-defined. However, subtraction is not closed under operation for the natural numbers; for example, 2 − 5 = −3 and −3 ∉ N, which implies that token subtraction is not well-defined. Even though Petri Nets impose constraints that can prevent subtractive violations of closure on N, this is not actually closure. Murata’s definition for Petri Nets in [1] only defines multiplicity mappings and markings for some countable sets, which should imply that such countable sets be closures of N under addition and subtraction.

[1] T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541–580, August 2002. Runestone1 (talk) 03:30, 13 June 2010 (UTC)

Please explain what alternative you have in mind and how Murata's article says anything about it. I'm looking at his definition ([1], page 3, table 2) and it describes flow multiplicity and markings as mappings to numbers just like everybody else. Rp (talk) 11:54, 7 April 2011 (UTC)

Apologies, I realise it has been a while. Not all number sets have the same closure properties under operation (here we are talking about addition and subtraction operations) and an example of closure violation was provided above. There are significant differences in closure properties between finite and infinite number sets under operations, where the natural number set is infinite. The remedy is very simple. For example, under "Syntax" you have for "Markings" places mapping to the natural numbers, which will violate closure under subtraction. You only need to use another number set, say Z, explain that Z is a subset of the integers closed under addition and subtraction and map S to Z. To convince you further, we can have finite number sets under modulo arithmetic to prevent closure violations. In fact, on a computer we only have finite number sets under modulo arithmetic, for example, if you have an unsigned integer equal to 10 and you subtract 11, then on a 32 bit machine the value would be 2^32 -1, which is closed under subtraction (that is, the number returned in in the set of positive integers less than 2^32). Runestone1 (talk) 04:46, 22 October 2011 (UTC)

Be careful not to use arguments like "... just like everybody else"; this is a kind of fallacy known as an appeal to popularity (or Argumentum ad Populum) and it can leave you wide open for logical attacks. The formal truth is that a thing is not true just because may people think it is true, we still need to apply reason. Some might say that the "everybody else" are experts, this would be an appeal to authority, which is also a fallacy; I am also an expert in this area, but as you can see above, I gave you reasoning rather than a statement from authority, and I did that because it is the reasoning that can assert truth in a statement. My authority (just like anyone else's authority) on the topic in fact asserts precisely nothing. Runestone1 (talk) 05:33, 22 October 2011 (UTC)

I'm sorry, but I fail to understand the purpose of your Z. Sets of markings aren't typically closed under subtraction: disallowing negative numbers of tokens in places is fundamental to the formalism and its applications. Rp (talk) 15:11, 22 October 2011 (UTC)

The point is that your definitions are not well-defined and Z as a closure under subtraction makes it well-defined. If someone wants to mathematically prove something about Petri Nets and they come to this Wiki for definitions with the assumption that the definitions here are well-defined, there are certain problems where they could easily arrive at the wrong conclusion in their proofs because they are not well-defined. By stating that Z is closed under operation in definitions will add the condition of closure, which will provide a necessary conditions for correct mathematical proofs concerning markings. As stated above, "Even though Petri Nets impose constraints that can prevent subtractive violations of closure on N,...", subtraction is not well-defined on the set of natural numbers; that is, this closure violation is a fundamental mathematical violation. Your argument of "...fundamental to the formalism and its applications" would be correct if a place and its markings were one thing and that thing were a number, and if the algebraic system for those numbers were defined and proven in the definitions for Petri nets, but neither is the case. The fact that places are one thing and their markings another, the burden of proving an algebraic system for the markings goes to some existing algebraic theorems; in which case, the correct algebra would need to be specified. One does need to state closure under subtraction to state the correct algebra even though lots of other authors have not (and probably because they do not understand algebra and number theory). If you want to understand better my argument here, you only need to investigate some undergraduate books on algebraic number theory. Runestone1 (talk) 00:17, 23 October 2011 (UTC)

I'm sorry, feel free to call me dense, but I just miss the point. Which definitions are ill-defined? Make the corrections yourself. Rp (talk) 01:18, 23 October 2011 (UTC)

Ah! Ha! Actually it should be me apologising then, because you write about discrete structures such as Petri nets, I had assumed you were coming from a discrete mathematics background; so, sorry about any false assumptions on my behalf. Saying "not well-defined" must have sounded absolutely dreadful, it is just a mathematical phrase relating to closure in this case or ambiguity in other cases and was not in any way a slur on your work with this Wiki etc. Actually, you have done a rather good job so far. If you are genuinely happy for me to make changes, then I'll be glad to help out. Runestone1 (talk) 07:27, 23 October 2011 (UTC)

I think I wrote that definition, but if a better one can be given, by all means do. But your claim that it's ill-defined because it uses subtraction of tokens and N isn't closed under subtraction is just wrong: the definition does not use subtraction of tokens, for exactly that reason. Rp (talk) 17:57, 23 October 2011 (UTC)

Well, lets analyse your claim. I may very well be wrong; if we make that assumption, then here are the conditions of my error: "consume" and "produce" are not aliases for "subtract" and "add", in which case you would need to show their fundamental mathematical axioms are different from those of "subtract" and "add". Or, I am not wrong and "consume" and "produce" are just aliases for "subtract" and "add" and your argument. In your definition you provide a program that explains an enabled transition firing and you claim that because you do not used subtract anywhere then no subtraction takes place. Let us consider another situation like yours where no subtraction operations occur. Concerning base 2 numbers, the value 1 may be exchanged with the value "true" and the value 0 with the value "false". That is, base 2 numbers may be represented with sequences to truth values and the subtraction operation may be written as a program on these truth value sequences that only uses Boolean logic operations (not, And, Or, XOr, etc.). Even though the subtraction of two numbers has been obfuscated by the details of the program, it would be false to claim that subtraction does not occur because only Boolean logical operations were applied... Similarly, you have a program in your definition that obfuscates the subtraction of tokens, but it does not eliminate the subtraction of tokens, even if the convention is to call this subtraction of tokens, "consumption". The fact remains that some multiplicity values have been subtracted from some token value in the firing of the transition, which is precisely why the multiplicity values and the token values belong to the same number set. Runestone1 (talk) 02:28, 25 October 2011 (UTC)

True, but none of this helps me see how this makes the definition ill-defined. This discussion is getting nowhere. If you see an error please point it out or correct it. Rp (talk) 22:59, 25 October 2011 (UTC)

Hi Rp, I have added some definitions (1,2 & 3) to the "Formal definition and basic terminology" section, hopefully this meets with approval. Here, the definition commits to countable sets (as with Murata's definition), but does not commit all the way to the Natural number set; the "Remark 1." has been added to indicate the possibility of different algebraic varieties of Petri nets, which could perhaps link to other Wikis on Petri nets. -- So, the Natural number set is a countable set, but not all countable sets are the Natural number set. The kind of countable set is not meaningful in the context of Petri nets, it only becomes meaningful in the application of Petri nets; but, if we say specifically the Natural number set then we commit Petri nets to certain applications (namely those that deal specifically with Natural numbers). My argument with closure is just to point out that not all applications will conform with a Natural number definition. A common application of Petri nets are Petri net diagrams used to communicate Petri nets; here, tokens are not elements of the Natural number set, but are elements of a countable set. Runestone1 (talk) 01:35, 26 October 2011 (UTC)

I appreciate your efforts thus far, but there are a couple of problems:

• In a lot of places you deviate from the usual Petri net terminology (using 'Petri net diagram' for 'Petri net', 'state' for 'place', 'configuration' for 'marking' etc.), which will be very confusing to readers; in some cases, the meaning isn't clear. Do return to the usual terminology (e.g. as used in the Rozenberg and Engelfriet article you cite).
• Moreover, you much extend the definition what a Petri net is, by allowing any countable set as a place marking; this makes the definition include coloured Petri nets, which were previously excluded, so you will have to do a lot of rewriting in the rest of the article to reestablish consistency.
• Considering the amount of changes required (and the fact that you are committing them in very small steps) it will be a while before this article is consistent again. In order not to penalize our readers too much, it may be better to revert what you've done thus far and edit a copy in some sandbox page instead. Rp (talk) 19:30, 26 October 2011 (UTC)

If you really do appreciate my efforts then why the last point? Moreover, did you even read the Rozenberg and Engelfriet article? Even they make the distinction between Petri net and Petri net diagram.

• See page 12 and I quote, "Graphically, a configuration C⊆P is represented by placing a "token" (i.e., a fat dot, or a thumbtack when we use transparencies) in every circle corresponding to a place in C. Hence a single token represents a local state of the system, often corresponding to the state of a component of the system. Since we mark the net with tokens, a configuration is also called a marking of the net". A place is a state, again, please actually read the article. In any case, I have made some changes to conform better with the existing material.
• You say, "this makes the definition include coloured Petri nets", which is precisely incorrect. A coloured Petri net involves such things as guards on transitions and functions that label the arcs; there has been nowhere where I have defined such things as to make my definitions include Coloured Petri nets. What you say is completely false, please read "Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical" by Kurt Jensen.
• I find this statement to be some very childish nonsense. Please, grow up. Runestone1 (talk) 02:21, 27 October 2011 (UTC)

Good luck with your efforts. Rp (talk) 08:13, 27 October 2011 (UTC)

Definition of net

The definition of a net In Formal Definitions... section describes P, T, and F. The sentence in the paragraph after that starting with "Moreover ..." gives two conditions on F. Are they a part of the definition of a net? In that case, I can make those two as sub-items of the description of F instead of in the paragraph. Abhay Parvate (talk) 06:37, 16 November 2011 (UTC)

There are some unclarities in there (e.g. it's debatable whether a Petri net is a state-transition system) introduced by recent edits. I'm hoping to resolve these all at once. Rp (talk) 22:58, 22 November 2011 (UTC)

Yes, the items are a part of the definition of a "net" and they do describe conditions for F, I agree, they fit better with F. Done! A Petri net is a state-transition system, because P ∪ T is a set of elements and F is a set of binary relations on the elements. That is, (P ∪ T, F) is a state-transition system. Runestone1 (talk) 07:03, 12 December 2011 (UTC)

Well, the markings with the firing relation are a state-transition system, so every Petri net is certainly equivalent to a state-transition system, but that is not exactly the same as saying that it is one. Furthermore, the reader shouldn't be led to assume that the number of states in the system is always finite: that is only true for bounded Petri nets. Rp (talk) 23:45, 18 December 2011 (UTC)

Rp you have not read clearly my comment, "That is, (P ∪ T, F) is a state-transition system". In addition, your argument about not assuming finite state sets is a straw man fallacy. Of course, one should not assume that the number of states is finite, but you're statement in this thread fails to add any new information and some implications in your argument are false, as I have never said or implied that state sets in Petri nets are always finite. I'm happy to have a reasonable argument with you, but then you will need to apply formal reason free of fallacious arguments. Runestone1 (talk) 05:31, 8 January 2012 (UTC)

Our attempts at having reasonable arguments have failed thus far, with no prospects of improvement. Hence I will refrain from any further attempts unless we change media. Rp (talk) 00:04, 9 January 2012 (UTC)

free choice net

Definition of the Free Choice Net seem to be incomplete. It does not fully describe outgoing arcs from transition. Any arc that is outgoing from transition does not satisfy neither condition. The outgoing arc from transition is NOT arc going from place. (obviously it is going from transition) The outgoing arc from transition is NOT arc going to a transition, as it is not allowed in petri nets. Is here sth, that I misunderstood? — Preceding unsigned comment added by 140.192.249.27 (talk) 00:24, 1 February 2012 (UTC)

I've attempted to fix the formulation, please check. Rp (talk) 17:22, 1 February 2012 (UTC)

Gene regulatory network

When I read this article, I got a strong feeling that the gene regulatory network is somehow related the Petri net, in particular the Gillespie algorithm is related to the timed Petri net. (Igny (talk) 03:50, 8 May 2009 (UTC))

All I know is that Petri nets are sometimes applied in this area, but I don't know any specifics. Rp (talk) 19:52, 25 June 2009 (UTC)

PS: Applications to biology are frequent, see e.g. here. Rp (talk) 14:22, 27 February 2012 (UTC)

sPN and ctMC, more details about the equivalence of models

It's written in the article the following text: "A subsidiary of timed Petri nets are the stochastic Petri nets that add nondeterministic time through adjustable randomness of the transitions. The exponential random distribution is usually used to 'time' these nets. In this case, the nets' reachability graph can be used as a Markov chain."

I had some dubts about the equivalence of the models and discovered that the equivalence sussists due to memoryless property of the exponential distribution. I read the answer from the article "A Class of Generalized Stochastic Petri Nets for the Performance Evaluation of Multiprocessor Systems" of Marsan, Balbo and Conte. I propose to explain why the two models are equivalent and also to link the exponential distribution property http://en.wikipedia.org/wiki/Exponential_distribution#Memorylessness. — Preceding unsigned comment added by 79.37.139.65 (talk) 16:47, 16 April 2012 (UTC)

Transitions with multiple forks

Something that's not entirely clear to me (a math novice) is whether a transition can have more than one fork (>2 outgoing arcs). This would make certain tasks like sorting tokens easier and I'd expect this to be perfectly valid (unless the pn is restricted to a state-machine or similar type) since it should also be valid for transitions to have >2 incoming arcs if I read the article correctly. Zoef1234 (talk) 17:02, 4 January 2013 (UTC)

Yes, it is valid (read the definition). Why do you call this 'multiple forks' - a fork can have more than two tines, can't it? Rp (talk) 00:39, 6 January 2013 (UTC)

Well yes, but fork() has 2 tines. Anyway, thanks(!) and a good day to you, sir. Zoef1234 (talk) 10:42, 7 January 2013 (UTC)

Definitions section

The definitions are a mess. I will edit them so that they'll be more solid and readable. I will use Murata's survey [2] as a principal source. Thachx (talk) 09:50, 17 April 2013 (UTC)

Please do! I don't know why there are two sets of definitions in the article. The term configuration should go, marking is standard. I gave up trying to fix the definitions after the discussion above, but if I can help let me know. Rp (talk) 09:23, 18 April 2013 (UTC)

Just a detail regarding "Restrictions", 1. state machine

It is claimed within the mentioned section, that in a state machine type petri net there cannot be concurrency. However, the only constraint given for the state machine type is $\forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1$

I believe this is not enough, in addition the whole net must be one connected component. Consider a net $(S,T,W)$ where $S=\{p_{1},p_{2}\},T=\{t_{1},t_{2}\},W=F\cup F^{-1}$ and $F=\{(p_{1},t_{1}),(p_{2},t_{2})\}$. I.e. 2 places with self loops. — Preceding unsigned comment added by RasTaIARI (talk • contribs) 12:28, 10 August 2012 (UTC)

You are correct; alternatively, the initial marking may be required to have exactly one token. I don't know what is common. Rp (talk) 14:23, 23 September 2013 (UTC)

Relationship with state machines

Dear all,

in Section Restrictions it is stated the following:

1. In a state machine (SM), every transition has one incoming arc, and one outgoing arc. This means, that there can not be concurrency, but there can be conflict (i.e. Where should the token from the place go? To one transition or the other?). Mathematically: $\forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1$

Unless I missed something this is not true. The concurrency in a Petri net is not due to the in/out degree of its transitions but to the fact that several places can contain tokens in a given marking. To get (something which can be seen as) a state machine one thus needs to consider a safe Petri net such that every transition has an in/out degree of one.

--Lowije (talk) 12:26, 23 September 2013 (UTC)

You are correct; alternatively, the initial marking may be required to have exactly one token. I don't know what is more common. Rp (talk) 14:42, 23 September 2013 (UTC)

I don't know what is more common either. In fact I am not sure that this is a classical relationship between Petri nets and FSA, I can't remember having read it anywhere else than on this wikipedia page (and on the corresponding french page which has the same mistake in it). Maybe requiring the initial marking to have exactly one token is better, as it is a simple structural property. Lowije (talk) 12:26, 23 September 2013 (UTC)

I agree; made the change. The observation that a finite state machine is a Petri net in which all branching happens on places is definitely commonplace. Rp (talk) 10:15, 24 September 2013 (UTC)

By the way, how would you propose to fix the way Petri nets are defined? My proposal would be to adopt the definitions in Reisig, 2013.

Notation is mixed

In the definitions of L and R, the notation L(N) and R(N) is used (with an obviously missing parameter). More downward on the page, L(N,M_0) and R(N,M_0) are used. — Preceding unsigned comment added by 2001:980:93A5:1:74EB:4D18:FB5D:EBB2 (talk) 18:18, 17 October 2016 (UTC)