Talk:Petri net

From Wikipedia, the free encyclopedia

Contents

[edit] 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)

[edit] Pedantic

This page seems overly pedantic. The opening, for instance, is filled with terms needing additional clarification:

discrete distributed systems generalize automata theory

Seems like a simpler, clearer statement is needed--and I'm not qualified! Can someone make this accessible to a layman like me?

No problemo! I'll get right on it. Vonkje 03:04, 8 Jun 2005 (UTC)

[edit] "Also known as"

Vonkje, I am not happy with the "also known as" clauses in your formal definition. E.g., a place is not a "file" or "other container", it is a place, an abstract notion. Similarly, I think your introduction uses the word transaction where it really doesn't belong. (One of the problems with Petri nets is that they cannot easily express transactions.)

yer right! ... I'll 'up 'n fix it. Vonkje 20:37, 9 Jun 2005 (UTC)

The formal part is good, although I have never seen a separation between arcs and arc weights before, nor have I seen the use of place capacities; I would suggest to omit the latter. Can you give a reference for this definition?

--Rp 17:17, 9 Jun 2005 (UTC)

I hadn't seen the separation either, until I attended a tutorial by Jörg Desel at the 4th ACPN in 2003. ... makes sense when you think about it more. The paper is called "What is a Petri Net" by Desel and Juhás.
By the way: Warm greetings from Leiden to Eindhoven (though I'm here in Florida for the summer). Vonkje 20:37, 9 Jun 2005 (UTC)

[edit] 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)

[edit] 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 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)

[edit] 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)

[edit] 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 ususal 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)