Petri Nets

I’m trying to build bridges between mathematics and practical subjects like ecology and engineering — subjects that might help us save the planet.

As part of this, I have a project to explain how some ideas from electrical engineering, control theory, systems ecology, systems biology and the like can be formalized — and to some extent unified — using “symmetric monoidal categories”. Whenever you have a setup with:

• abstract gadgets that have ‘input wires’ and ‘output wires’,

and you can

• hook up these gadgets by connecting outputs to inputs,

and

• the wires can cross over each other, and

• it doesn’t matter whether one wire crosses over or under another

then you’ve probably got a symmetric monoidal category! For a precise definition, and lots of examples, try:

• John Baez and Mike Stay, Physics, topology, logic and computation: a Rosetta Stone, in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-174.

Back then I was excited about examples from ‘topological quantum field theory’, and ‘linear logic’, and ‘programming semantics’, and ‘quantum circuit theory’. But now I’m trying to come down to earth and think about examples of a more everyday nature. And they turn out to be everywhere!

For example, when you see these diagrams:

you may see a 10-watt amplifier with bass boost, and 16-volt power supply with power-on indicator light. But I see morphisms in symmetric monoidal categories!

Back in week296 I explained a symmetric monoidal category where the morphisms are electrical circuits made only from linear resistors. It’s easy to generalize this to ‘passive linear circuits’ where we include linear inductors and capacitors… and we can keep going further in this direction. I’m writing a paper on this stuff now.

But today I want to head in another direction, and tell you about something I’m beginning to work on with Jacob Biamonte: something called ‘Petri nets’.

Before I do, I have to answer a question that I can see forming in your forehead: what’s the use of this stuff?

I don’t actually think electrical engineers are going to embrace category theory — at least not until it’s routinely taught as part of college math. And I don’t even think they should! I don’t claim that category theory is going to help them do anything they want to do.

What it will do is help organize our understanding of systems made of parts.

In mathematics, whenever you see a pattern that keeps showing up in different places, you should try to precisely define it and study it — and whenever you see it showing up somewhere, you should note that fact. Eventually, over time, your store of patterns grows, and you start seeing connections that weren’t obvious before. And eventually, really cool things will happen!

It’s hard to say what these things will be before they happen. It’s almost not worth trying. For example, the first people who started trying to compute the perimeter of an ellipse could never have guessed that the resulting math would, a century or so later, be great for cryptography. The necessary chain of ideas was too long and twisty to possibly envision ahead of time.

But in the long run, having mathematicians develop and investigate a deep repertoire of patterns tends to pay off.

Petri nets – the definition

So: what’s a Petri net? Here’s my quick explanation, using graphics that David Tweed kindly provided for this article:

Petri net, Azimuth Project.

A Petri net is a kind of diagram for the describing processes that arise in systems with many components. They were invented in 1939 by Carl Adam Petri — when he was 13 years old — in order to describe chemical reactions. They are a widely used model of concurrent processes in theoretical computer science. They are also used to describe interactions between organisms (e.g. predation, death, and birth), manufacturing processes, supply chains, and so on.

Here is an example from chemistry:

The circles in a Petri net denote so-called states, which in this example are chemical compounds. The rectangular boxes denote transitions, which in this example are chemical reactions. Every transition has a finite set of input states, with wires coming in from those, and a finite set of output states, with wires going out. All this information can equally well be captured by the usual notation for chemical reactions, as follows:

C + O2 → CO2

CO2 + NaOH → NaHCO3

NaHCO3 + HCl → H2O + NaCl + CO2

One advantage of Petri nets is that we can also label each state by some number (0,1,2,3,…) of black dots, called tokens. In our example, each black dot represents a molecule of a given kind. Thus

describes a situation where one atom of carbon, one molecule of oxygen, one molecule of sodium hydroxide, and one molecule of hydrochloric acid are present. No molecules of any other kind are present at this time.

We can then describe processes that occur with the passage of time by moving the tokens around. If the carbon reacts with oxygen we obtain:

If the carbon dioxide combines with the sodium hydroxide to form sodium bicarbonate, we then obtain:

Finally, if the sodium bicarbonate and hydrochloric acid react, we get:

Note that in each case the following rule holds: for any given transition, we can delete one token for each of its input states and simultaneously add one token for each of its output states.

Here is a simpler example, taken from this article:

Petri net, Wikipedia.



Here the transitions are denoted by black rectangles. This example is somewhat degenerate, because there no transitions with more than one input or more than one output. However, it illustrates the possibility of having more than one token in a given state. It also illustrates the possibility of a transition with no inputs, or no outputs. In chemistry this is useful for modelling a process where molecules of a given sort are added to or removed from the environment.

Symmetric monoidal categories

Now, what about symmetric monoidal categories? If you really want the definition, either read theRosetta Stone paper or the nLab article. For now, you can probably fake it.

A symmetric monoidal category is, very roughly, a category with a tensor product. If we ignore the tokens, a Petri net is a way of specifying a symmetric monoidal category by giving a set of objects x_1, \dots, x_n and a set of morphisms between tensor products of these objects, for example

f_1 : x_1 \otimes x_2 \to x_2 \otimes x_2

f_2 : x_2 \to 1

f_3 : 1 \to x_1

where 1 denotes the tensor product of no objects. For example, the objects might be molecules and the morphisms might be chemical reactions; in this case the tensor product symbol is written ‘+‘ rather than ‘\otimes‘.

The kind of symmetric monoidal category we get this way is a ‘free strict symmetric monoidal category’. It’s ‘free’ in the sense that it’s ‘freely generated’ from some objects and morphisms, without any relations. It’s ‘strict’ because we’re assuming the tensor product is precisely associative, not just associative ‘up to isomorphism’.

For more on how Petri nets describe free symmetric monoidal categories, see:

Vladimiro Sassone, On the category of Petri net computations, 6th International Conference on Theory and Practice of Software Development, Proceedings of TAPSOFT ’95, Lecture Notes in Computer Science 915, Springer, Berlin, pp. 334-348.

Here Sassone describes a category of Petri nets and sketches the description of a functor from that category to the category of strict symmetric monoidal categories. Sassone also has some other papers on Petri nets and category theory.

As I mentioned, Petri nets have been put to work in many ways. I won’t even start trying to explain that today — for that, try the references on the Azimuth Project page. My only goal today was to convince you that Petri nets are a pathetically simple idea, nothing to be scared of. And if you happen to be a category theorist, it should also be pathetically simple to see how they describe free strict symmetric monoidal categories. If you’re not… well, never mind!

60 Responses to Petri Nets

  1. DavidTweed says:

    Trifling point: I believe NaHCO_3 is bicarbonate of soda, sodium carbonate is apparently Na_2CO_3. (Feel free to delete this comment.)

  2. John Baez says:

    I’ll fix that, thanks. It’s worth keeping your comment visible as a reminder: sodium bicarbonate is the one that doesn’t have two of anything.

    In fact the term bicarbonate is officially deprecated by the official society in charge of chemical names, because it doesn’t make sense. But people keep using it.

  3. Web Hub Tel says:

    Once again this is the greatest blog.

    I had no idea that Petri Nets started as descriptions of chemical reactions. It seems to me that this path leads more directly into Stochastic Petri Nets where you can actually apply probabilities to determine likelihoods of place occupancy. All the chemical reactions would also need to show the “reverse” Petri Net representations to indicate the full equilibrium (this may require photons to generate transitions).

    I always wondered why Petri Nets didn’t catch on bigger. Software people use these things called Activity Diagrams, which are a hybrid mishmash of the PN concept. Those things are badly abused though.

    And I like the mention of category theory, which goes nicely with your mention of bond graphs of awhile back.

    Incidently, whenever I see category theory mentioned, I think of Robert Rosen and his work on biological systems. This is an obscure article of his “On Models and Modeling”. That is Azimuth-level material because it gets you thinking.

    Thanks!

    • Tim van Beek says:

      Software people use these things called Activity Diagrams, which are a hybrid mishmash of the PN concept.

      Activity diagrams are part of the unified modelling language (UML). UML is much richer than petri nets, and there are parts that are supposed to model software, and parts that are supposed to model interactions of users and software, activity diagrams are often used for the latter.

      • WebHubTel says:

        Whenever someone shows an Activity Diagram at a review and I point out a deadlock or race condition in their multitasking design, they get mad at me. The problem with UML is they treat formalism as an afterthought, with the UML companies marketing their tools to make as many people as happy as possible. More happy people means more sales, however poorly that translates to correct design for concurrency.

        Edward Lee at UC-Berkley put it bluntly with his classic paper “The Problem with Threads”. Incidently, he has recently released a free book on embedded systems.

        • Tim van Beek says:

          I’m not sure if there is any graphical language that is suitable for the design of multithreading systems, although many have been designed over the years. I suspect that multithreading will always be very hard to understand for humans…

          WebHubTel said:

          Whenever someone shows an Activity Diagram at a review and I point out a deadlock or race condition in their multitasking design, they get mad at me.

          Hmm, I do hope you don’t yell at people something like “what you call a design is obviously flawed, every idiot can see that…”.

          But seriously, if people get mad at you there is usually something that you can do about it by adjusting your behaviour. Before you tell people about their mistakes, you should make clear that

          a) you honestly try to understand what they have done,

          b) appreciate their competence,

          c) understand when and where they have been sloppy on purpose rather than due to incompetence.

          Then maybe it may be a good tactial decision to state your remark in the form of a question rather than an attack.

          Very few people are thankful of someone else telling them that something they have done is obviously wrong because…

          Many geniuses have to learn this the hard way, some never do (did you ever wonder why Einstein was unable to get employed in academia after he got his diploma?).

        • Web Hub Tel says:

          Tim, Yes its probably my fault for not being diplomatic. There are two basic rules for using Petri Nets to model concurrent systems. Rule #1, you have one token per thread. Rule #2, you make sure all threads loop back on themselves or have a clear exit state. I find #2 violated quite often in activity diagrams, pointing out that it will lead to thread exhaustion (which is similar to a mass-action law in chemical reactions). And my problem is that I don’t have a diplomatic way of phrasing that.

        • Tim van Beek says:

          Web Hub Tel said:

          And my problem is that I don’t have a diplomatic way of phrasing that.

          I don’t have one, either, “thread exhaustion” should be known to anyone who models multithreading systems. Here is what I would try to say in a situation like that: “Sorry folks, my understanding of ‘thread exhaustion’ is blahblah, I have been told that this has to be addressed by blabla, now I’m kinda confused that I don’t see enough of blabla in your model…” etc.

          Back to Petri nets:

          Rule #1, you have one token per thread. Rule #2, you make sure all threads loop back on themselves or have a clear exit state.

          Ok, I begin to see how Petri nets could be used here, but in addition we’d need we need special states where a new thread can start. A state would be characterized by shared editable data, because that’s where multithreading comes into play. Then the order of threads entering the same state would be important, but Petri nets don’t care about the order (as I learned from remarks by David Tweed below).

          Secondly, we’d need some priority concept for threads, and we’d need to model how the system limits the number of active threads by not creating new ones or letting existing ones sleep, besides letting existing ones finish. Do all of these aspects become part of a Petri net model?

        • Web Hub Tel says:

          Tim, I would consider that C.A.R. Hoare’s classic text called “Communicating Sequential Processes” a valuable resource. (Free electronic copy!)

          CSP’s are one model for concurrency-based languages, Ada being an example. I can translate any working Petri Net directly into Ada code by applying Hoare’s rendezvous concept to a transition place. But realistically few people use Ada.

          Assigning thread priorities is not always needed in a design, especially in a simulation where you can apply discrete event methods to model instantaneous computation.

    • John Baez says:

      Glad you liked my post, Web Hub Tel!

      Indeed, the applications of Petri nets to chemical reactions all seem to use stochastic Petri nets… and those are what Jacob Biamonte and I are actually working on right now. This post didn’t get around to talking about those… maybe later.

      Software people use these things called Activity Diagrams, which are a hybrid mishmash of the PN concept. Those things are badly abused though.

      Thanks for letting me know – both of the existence of these diagrams, and their ‘abuse’. I’m trying to slowly sift through various diagrammatic languages and extract their category-theoretic meaning. But as you note below, when people design a language to ‘make as many people happy as possible’ and ‘treat formalism as an afterthought’, this language can easily become a complicated mishmash from an abstract theoretical perspective, even if it’s practical and most people like it.

      So, for my theoretical work I’ll try to start with diagrammatic languages that are ‘pure and simple’, and if getting ahold of these requires taking existing languages and mentally removing lots of features, that’s what I’ll do.

      Thanks for pointing out Unified Modeling Language, Tim! I have it in my database of diagrammatic languages, but I haven’t gotten around to studying it. Even if it is a ‘mishmash’, I’m sure it’ll be full of interesting concepts which I can separate out and study.

    • Aaron Denney says:

      I once worked with a professor that pushed Petri nets as a generalized concurrency abstraction and proof tool. That was actually my problem with them — they seemed _too_ general, and at the same time _unwieldy_ for expressing the things I wished to express.

      • John Baez says:

        I wouldn’t want to write most programs in a Petri-net-based language. On the other hand, I wouldn’t want to program with Turing machines, either — yet they’ve served as a good framework for investigating some theoretical issues. Maybe Petri nets are a good framework for theoretical issues related to concurrency, in a similar way. I don’t know.

        I’m coming to the subject from a different angle. What I like is using Petri nets to describe chemical reactions, at least after we assign a “reaction rate” to each transition. If you’re not permanently scarred by your previous experience, I recommend taking a quick peek at:

        • Darren J. Wilkinson, Stochastic Modelling for Systems Biology, Chapman and Hall, New York, 2006.

        It may give you a different outlook on Petri nets!

  4. John F says:

    One word: LabVIEW. Your bulleted definition of symmetric monoidal categories was implemented as a programming language about 20 years ago.

    http://www.ni.com/labview/

    Electrical engineers (in the US anyway) probably have more experience and need to use LabVIEW then any other programming environment. There was a time, say 15 years ago, we would say NI makes great data acquisition hardware but their software needs work. Now it’s almost the other way around, except their hardware is still pretty good.

    FWIW, LabVIEW is the standard programming environment for robotics for a number of reasons. One is still that often there is no good substitute for a NI hardware component. Another is that, like Matlab, it works. And has a large user repository. High school and younger students have to use versions of LabVIEW in the FIRST competitions.

    http://www.usfirst.org/

  5. Phil Henshaw says:

    As Robert Rosen pointed out, with his diagram of the relation between formal and physical systems, there is a matter of “encoding and decoding” in going back and forth. You still have the problem of discovering what abstract analog seems to correspond to the complex natural system you’re representing.

    So far I’ve been generally unable to interest modelers in studying the physical system their models are intended to be analogs of… is the problem. It seems caused by disinterest in the difference between information constructs and physical ones, they’re different. One only works in the mind and the other only in the world.

    What you find is that the regularities of physical systems that models are based on are temporary. If you are not going back and forth all the time your model will lose touch with reality.
    Models Learning Change.. http://www.cosmosandhistory.org/index.php/journal/article/view/176/295

    • Web Hub Tel says:

      I hear you Phil. The model of oil depletion that you reference in your paper is one of those thorny problems that people don’t want to continuously adapt to reality. They realize that it exists but don’t put the effort into getting a better quantitative understanding (climate scientists are doing a better job of this IMO).

      Incidentally, I just posted my own massive tome on oil depletion, called http://TheOilConundrum.com. I had models coming out my ears to try to understand this topic and I put about 5 years of off-hours effort into it. It’s an AzimuthProject topic that I hope to contribute to in some way.

    • John Baez says:

      Phil wrote:

      So far I’ve been generally unable to interest modelers in studying the physical system their models are intended to be analogs of…

      I’ve been reading old papers about systems ecology, and there the modelers seemed quite acutely concerned about the deficiencies of their models (which were indeed substantial).

      But let’s face it. With all the lumps and bumps airbrushed away, models seem better than the real thing. They’re alluring, seductive. That’s why they’re called models.

      • Phil Henshaw says:

        John, you’re quite right on both, that there was a generational shift away from studying the relation of natural systems and theoretical ones, partly made possible by models being so very seductive as replacements for real systems. I think it also developed from more natural causes, that as we successively multiplied the complexity of all our systems and interactions with each other and the environment it’s had a true numbing effect on our minds, leaving us handicapped, and making it harder and harder to point out the deep errors the theory people have been making.

        It is indeed “odd” that we now are seeing so many clearly documentable ways in which science has let itself become sophistry, with great consequence it seems. The social dimension of that is how everyone is avoiding discussion of. I think at root the question is whether you think nature *is* a network of Platonic ideals (a model), or that networks of Platonic ideals have some remarkable but limited usefulness.

        The latter option gives you the best of both approaches to studying the natural world, and the former leaves you quite blind to the natural world and really unable to learn from it.

    • Phil Henshaw says:

      Web Hub Tel, When people don’t keep studying how the environment might do something different from their model, it gets harder and harder to tell when it already did some time ago. You just can’t anticipate change in a model unless you keep going to the effort of understanding the whole system you’re trying to model some part of.

      For the world economy we’re at an “overshot start-up” phase in building modern civilization, still projecting infinite expansion when already being physically knocked down by collapsing component and environmental systems. The great majority of people have not noticed yet that reality went some other way than the model projected. I’m getting consistent positive feedback from other systems ecologists on an idea about what to expect at natural resource limits, when you find the price mechanism switching from being cost regulated to scarcity regulated. That’s would reflect growing demand moving from an welcoming to a resistive environment, from a positive sum to a zero sum game. Models would need to contain dynamic boundary condition assumptions, of environmental response.

      I don’t have any models though, but what I described conceptually in my OilDrum article http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=site:www.synapse9.com+commodities in “Profiting from Scarcity”. Conditions of growing demand in the face of scarcity can result in explosive price increases, and profit increases. The effect depleting resources would be to rapidly accelerate it, and hasten the EROI point of physical system bankruptcy. The main behavior change is from prices set by production cost and stabilized by increasing and decreasing supply, to determined by scarcity to go as high as needed to shut enough demand out to the market.

      That’s what I think you are seeing in the 00’s commodity boom, http://www.synapse9.com/issues/92-08Commodities.jpg with the whole spectrum of commodities following some hidden growth mechanism, indicating to me a world systemic resource limit of some kind, from how they’re connected. Now that a lot of demand has been wrung out of the world economy… it seems commodity prices will now just go back up higher with growing demand, until another wave of profiting from scarcity sweeps another wave of “retirements” across the world.

      That most people never realized that growth could ever run into complications and exhibit scarcity for the system as a whole, is interesting. It’s both not a good excuse, of course, and a marvelously simple bit of evidence. Doesn’t that show how we’ve been frequently thinking of the natural world as being nothing but our inherited cultural idea and information about it, and maybe that’s why we don’t check our models very often?? ;-)

  6. Tim van Beek says:

    John: The first time you mention “token” and write

    Otherwise there are no molecules of any other sort.

    …shouldn’t it be “there is no other molecule that is an input instead of a result of a reaction”? (For example there is CO_2, which is not on the list of “molecules = tokens”).

    • John Baez says:

      I wrote:

      In our example, each token represents a molecule. Thus

      describes a situation with one atom of carbon, one molecule of oxygen, one molecule of sodium hydroxide, and one molecule of hydrochloric acid. Otherwise there are no molecules of any other sort.

      Tim wrote:

      …shouldn’t it be “there is no other molecule that is an input instead of a result of a reaction”? (For example there is CO2, which is not on the list of “molecules = tokens”).

      What I meant is that the diagram above describes a situation in which no molecules of CO2, NaHCO3, H2O or NaCl are present right now. That’s why those circles don’t have black dots in them. There is one atom of C, one molecule of O2, one molecule of NaOH, and one molecule of HCl. That’s why those circles each have one black dot in them.

      I’m not trying to say anything about “inputs” and “outputs” here — I’m trying to explain what it means to have a certain number of black dots (“tokens”) inside a given circle (“state”).

      I’ve tried to rewrite my blog entry (and the Azimuth Project page) to make it clearer.

  7. Tim van Beek says:

    The description of chemical reactions with Petri nets is very remindful of finite state machines.

    A finite state machine has a finite set of states and transitions between the states based on certain conditions. It is often used to explain the term regular expression: Let’s say there is an infinite input string and we search it for a certain pattern, for example “aabb”. The computer program that searches for this pattern can be modelled as a finite state machine. It starts in the state “nothing found”. Once there is an “a” in the input, it changes to the state “one a found”. If the next character is an “a”, it changes to the state “two a’s found”, if it is not, it changes to the state “nothing found”.

    A regular expression is a search pattern such that the machine needs only a finite amount of memory. Be warned: Most people define regular expressions in a different way and later prove the equivalence to the definition above, however. “aabb” is obviously a regular expression.

    Since John seems to like a littel puzzle now and then, here is one: Find a search pattern that is not a regular expression (or prove that there aren’t any).

    (This stuff is usually taught in introductory classes of theoretical computer science as a part of either automata theory or formal languages.)

    • DavidTweed says:

      One of the minor differences between state machines and Petri nets is that by having multiple “present” things Petri nets don’t care about certain kinds of ordering things. Consider, e.g., modelling a penalty in soccer. There’s the penalty box area (“the box”), and there’s got to be contact between an attacking player with the ball and a defender, but before you get to the contact you might want to start the model with “there’s a defender in the box” state node and “threre’s an attacker in the box” state node and transition to a “potential for a penalty” state node. In theory either the attacker or the defender could enter the penalty box first, so a strict state machine would deal with this by having two separate paths leading to the “potential for a penalty” state just to model this “order isn’t relevant”. In contrast, the Petri net naturally allows tokens to arrive on the state nodes in either order and then, once there’s one token on each, will make the transition to the “potential for a penalty” state node.

      (Actually, my limited experience with Petri nets has been entirely based around using them for this type of task where you need multiple “preconditions” to arise and then a transition takes place.)

      • Giampiero Campa says:

        One of the minor differences between state machines and Petri nets is that by having multiple “present” things Petri nets don’t care about certain kinds of ordering things.

        Exactly. But in general logic tells me that the formalisms should be equivalent, in the sense that given a petri net you can build an equivalent FSM, and viceversa, with the petri net probably being more “compact”.

        Since chemical reactions express concentrations that change continuously in time, (therefore there is a continuous flow trough the transitions) i am not sure that this it the best formalism for chemical reactions, (perhaps stuff like block diagrams or signal flow graphs could be better) but it is indeed cool.

        More generally i wonder, once you model the system as a series of equations involving objects and morphisms, how do you actually go to “solve” the system, or propagate the state in time.

        I also wonder whether “initial” and “final” states would be a better terminology than “input” and “output” states.

    • John Baez says:

      Tim wrote:

      The description of chemical reactions with Petri nets is very remindful of finite state machines.

      Sammy Eilenberg, one of the founding fathers of category theory, shocked everyone when he quit working on the applications of category theory to algebraic topology and started working on finite state machines.

      The reason he did this is because finite state machines can be understood very beautifully in terms of category theory. He wrote a book about this:

      • Samuel Eilenberg, Automata, Languages and Machines, 1974.

      I have to admit I sort of enjoy having a role model of someone who started out applying categories to “high-class” pure math topics like algebraic topology, and then switched towards applying “lower-class” applied math topics like computation. Of course I don’t seriously believe there is a real distinction between “high-class” and “low-class” mathematics, but to a certain kind of pure mathematician, algebraic topology (or superstring theory) seem very sophisticated and prestigious, while finite state machines (or electrical circuits) seem sort of grubby and low-class. So, it takes a certain toughness to switch research directions from the former to the latter.

      I’ll have to think about your puzzle later! I should, in principle, know something about various classes of languages and the kinds of automata that can recognize them.

      David wrote:

      One of the minor differences between state machines and Petri nets is that by having multiple “present” things Petri nets don’t care about certain kinds of ordering things.

      Yes! This happens quite naturally as we move from categories to symmetric monoidal categories. The fact that we can use one dot to denote the current state of a finite state machine, but we can have more than one token on a Petri net, comes from this.

      There is a lot more to say about this, most of which I don’t know…

      • Todd Trimble says:

        John B added:

        Sammy Eilenberg, one of the founding fathers of category theory, shocked everyone when he quit working on the applications of category theory to algebraic topology and started working on finite state machines.

        The reason he did this is because finite state machines can be understood very beautifully in terms of category theory.

        Actually, I heard a rumor that he did this at least in part to secure funding for category theory or category theorists, perhaps at a time when certain powers were becoming skeptical of the pure-math applications of category theory. (I actually have reason to believe this rumor, because I think I remember from whom I heard it.)

        Sammy Eilenberg was a clever fellow.

      • Tom Leinster says:

        Is that Saunders Mac Lane I see sprouting out of the top of Eilenberg’s head?

    • DavidTweed says:

      Regarding Tim’s puzzle, I’m not sure how he’s defining “search pattern”, so this might be wrong. Suppose you simplify from searching to just “does this string match this regular expression”. Then you can’t express “is this string (of arbitrary length) a palindrome?”, whereas you can ask “does it contain palindromes up to length N (just enumerate them all as alternatives and “factorise”) or “is it only $b$s (using “b*”).

      But that not be what Tim was considering as a “search pattern”.

      • Tim van Beek says:

        David said:

        Regarding Tim’s puzzle, I’m not sure how he’s defining “search pattern”…

        A “search pattern” in my sense is a property that at most one finite substring of an infinite input string can have, like

        – be the first substring that starts with ‘a’, contains after that arbitrarly many ‘b’ and ‘c’ and ends with an ‘a’ (regular),

        – be the longest palindrome (not regular),

        so your example is a valid answer :-)

  8. Vasileios Anagnostopoulos says:

    Why my posts are not listed?

    • John Baez says:

      Sorry, your latest comment had a lot of links, so the automatic spam detection system classified it as spam! I will make that comment appear now. If other comments of yours were lost permanently, I apologize – I don’t see them now.

  9. Vasileios Anagnostopoulos says:

    If you like Petri nets take a look at “Process Algebras” that have recently been seen from a categorical point of view and they are more general I think.

    Wikipedia uses the term “process calculus ” that I do not agree.

    Intro : http://staff.science.uva.nl/~alban/DPM/process-algebra.pdf

    The definitive reference is : http://www.few.vu.nl/~wanf/books.html

    The connections are

    http://intlpress.com/HHA/v10/n1/a16/pdf

    http://www.pps.jussieu.fr/~gaucher/GaucherATMCS.pdf

    a thesis

    http://alexandria.tue.nl/extra1/wskrap/publichtml/9615633.pdf

    It also has some connection with model theory.

  10. John Sidles says:

    Baez says: “I’m trying to slowly sift through various diagrammatic languages and extract their category-theoretic meaning.”

    Among mechatronic engineers, the most popular such language (by far) is LabView’s “G”.

    What’s unique about G is that the most natural programming style uses *no* symbolic names at all … everything is just wires and ideograms (called “vi”‘s). The meaning of G code resides solely in the topology of the wires and the choice of ideograms connected by those wires … thus G is effectively a (uniquely?) “gauge” invariant language … where “gauge” is a shorthand for “arbitrary variable names.”

    In consequence, G is the *only* language where one can pass Student A’s thesis software to Student B … with a reasonable expectation that Student B will be able to “see” what the code means … without ever having to “decode” it.

    • John Baez says:

      I discovered “G” when looking at John F’s link to the Labview website. There’s a bit about G there.

      I know about a dozen different diagrammatic languages invented in different disciplines, and I keep finding more. I think category theorists will enjoy hearing some of these languages explained using their language. Whether the practioners of all these specific disciplines will enjoy seeing their languages related to each other by means of yet another language is yet to be seen.

      • John Sidles says:

        You might take a look also at the LabView resource on Polymorphic Functions and Units … here the deep isomorphism of G to category theory rises very near the surface.

      • Giampiero Campa says:

        Whether the practioners of all these specific disciplines will enjoy seeing their languages related to each other by means of yet another language is yet to be seen.

        It would be interesting to find out. But, assuming you don’t openly criticize any of those languages, i think everyone would be ok, if not happy.

        Overall it looks a like a Rosetta Stone, perhaps it could eventually form the basis of a tool to translate some of these visual languages into one another. It definitely would make people (non-mathematicians) more interested to category theory.

        Anyway, while we are at it, control engineers mostly use Simulink as a visual “programming language”, although i think the tool is seen more like a visual modeling language for dynamic systems. The abstraction yields a continuous data flow through all the subsystems (each having input, state and output vectors, related by either ODEs or FSMs), so there are no “Tokens”. There is a 2 minutes video here that explains the basics, but this is basically an implementation of the typical block diagrams that systems and control engineers draw on blackboards all the time.

        • WebHubTel says:

          Simulink has a problem with feedback loops and the latency of the delta-time update in solving differential equations conveniently. The problem is that it is not declarative and is solely data-flow. The tool Modelica and others like that supposedly fix that problem, in that the connections are implicitly 2-way, in line with the way that a mathematician would lay out the problem. Modelica is thus a component-based way of building up equations ala somehing like Mathematica.
          Models+Mathematica = Modelica is the mnenomic.

        • Giampiero Campa says:

          Hi WebHubTel.

          I think that by “feedback loops” you actually mean “algebraic loops” which are feedback loops in which all elements are systems without any dynamics. There are ways around such loops (like inserting a small delay of solving the loop explicitly), but if you don’t adopt any of them then the solver will do the work of solving the loop at each step, which slows down the simulation.

          Algebraic loops tend to arise more often when you model interconnections of physical systems. If you need to model physical systems, then yes it is actually easier to use a language like Modelica or Simscape, along with 2-way wires that share (instead of just transfer) information among subsystems.

          However if you want to model something like, say, a signal processing system, (or any data-flow system) then you are better off using something like Simulink or Scicos.

          Ideally the best option is using an environment in which you can use all these paradigms together, like interfacing physical systems described in a declarative language, with data flow systems, and with systems whose behavior is better modeled using state charts.

        • Web Hub Tel says:

          Yes Giampiero Campa, that is what I was getting at. The classic kinds of cases that I have run across involve engineers that write Simulink diagrams that consist of several blocks that appear to consume the drawing space. When I ask them to present a mathematical relation it has often consisted of a +, – and *. Much of it is extra baggage because they have to make it data-flow instead of declarative, which requires corrective measures to simulate the bi-directional flow. They enjoy doing this though because in the end it is all just a puzzle. Not much you can do, and yes Simulink makes up for it in real data-flow apps.

        • Phil Henshaw says:

          Giampiero & Web, it almost sounds like you’re talking about a fairly common engineering practice similar to what I’m trying to suggest for complex environmental systems, combining diagnostic monitoring, theoretical models and study of their organizational changes, as a way to more successfully interact with them. The mysteriously common cases are the ones where the models and the observed behavior entirely conflict and people just shrug it off and say they’re hoping to change how nature works someday… instead of their model.

          That problem often seems due to the very complexity of natural systems, seeming to force people to define them with the same theories their models depict. That then also prevents them from having an independent way to account for their conflicting observations independent of fitting their theory. If they don’t fit, the only response is to “draw a blank”. It’s a natural problem for complex systems it seems, that they’re hard enough to grasp, we turn them into information objects which keep us from thinking what they are and how they behave on their own. Once people appreciate the difficulty I have methods for making them more identifiable and relating models to their observed behavior, to find some more questions that are answerable.

          Do either of you know of examples where people are trying to do what you’re discussing, but with complex natural systems, say, considered as cells of organization you could locate but not concretely define?

      • John Sidles says:

        Now all we need is a koan … “What is the abstraction that has no name?”

        The (wholly visual) answer is a G panel, a SimuLink diagram, or any of the artworks from Karl Heinrich Hofmann’s Commutative Diagrams in the Fine Arts (Notices of the {AMS}, June/July 2002).

  11. […] The following post has nothing to do with the “Dear John” TV show, as you might have guessed, seeing that screen shot. I just used the title – this post is inspired with John Baez’ latest post on Petri nets. […]

  12. John Baez says:

    By the way, there seem to be two common variants of the definition of ‘Petri net’ that I gave in this blog entry.

    In the first definition, any transition can have at most one wire going to any of its input states, and at most one going to any of its output states. In this case a Petri net amounts to this:

    We have a set S of states, a set T of transitions, a function

    i: S \times T \to \{ \mathrm{false}, \mathrm{true} \}

    saying whether a given state is an input of a given transition, and another function

    o: S \times T \to  \{ \mathrm{false}, \mathrm{true} \}

    saying whether a given state is an output of a given transition.

    In the second definition, a transition can have any finite number of wires going to any of its inputs, or to any of its outputs. Then a Petri net consists of this:

    We have a set S of states, a set T of transitions, and functions

    i: S \times T \to \mathbb{N}

    o: S \times T \to  \mathbb{N}

    saying how many times a given state is an input or output of a given transition.

    I’ve seen one book where the first kind are called ‘Petri nets’ and the second kind are called ‘generalized Petri nets’.

    It’s the second kind that I was talking about in my blog entry, though my examples happened to be all of the first kind.

    Either way, you’ll notice that the definition has two symmetries. We can switch the functions i and o, or we can switch the sets S and T.

    The first symmetry corresponds to time reversal: we are switching inputs and outputs.

    The second symmetry is more interesting. We can call it duality: we are switching states and transitions!

    (I’ve seen books that use ‘duality’ to mean the result of applying both these symmetries.)

    Duality means that given the free strict symmetric monoidal category C on some set of objects and some set of morphisms, we can get a new free symmetric monoidal category C^* where the generating objects and morphisms have been switched!

    This is kind of surprising.

  13. Hi John,

    Nice post! It’s cool to think of both electrical circuits and chemical reactions as symmetric monoidal categories. One of the things I am trying to do is to figure out how electrical circuits and chemical networks might be related. The goal is to understand the biochemical networks that orchestrate the cellular symphony, using insights from circuits.

    Though Carl Petri invented his nets to represent chemical reaction networks, I don’t know if they were used much to study these networks. The first application I know of in this direction is some rather recent work by David Angeli with Patrick DeLeenheer, and Eduardo Sontag. See, for example, A Petri Net approach to the study of persistence in chemical reaction network.” and On modularity and persistence of chemical reaction networks.”

  14. Is there a preview option for the comments that I’m missing?

    • John Baez says:

      Manoj wrote:

      It’s cool to think of both electrical circuits and chemical reactions as symmetric monoidal categories.

      Yes, it raises interesting questions. By the way, I think of an electrical circuit as a morphism in a symmetric monoidal category. I think of a chemical reaction network or Petri net as specifying a symmetric monoidal category; then an allowed sequence of reactions is a morphism in this category. In both cases you can compose morphisms (which means composing circuits or sequences of reactions in series), and tensor (which means doing them ‘side by side’).

      One of the things I am trying to do is to figure out how electrical circuits and chemical networks might be related. The goal is to understand the biochemical networks that orchestrate the cellular symphony, using insights from circuits.

      Nice. What sort of insights? I recently spotted an interesting paper that combines two themes I’ve been pondering lately: chemical reaction networks and the Hopf bifurcation.

      • Mirela Domijan and Markus Kirkilionis, Bistability and oscillations in chemical reaction networks.

      Here’s the abstract:

      Abstract: Abstract bifurcation theory is one of the most widely used approaches for analysis of dynamical behaviour of chemical and biochemical reaction networks. Some of the interesting qualitative behaviour that are analyzed are oscillations and bistability (a situation where a system has at least two coexisting stable equilibria). Both phenomena have been identified as central features of many biological and biochemical systems. This paper, using the theory of stoichiometric network analysis (SNA) and notions from algebraic geometry, presents sufficient conditions for a reaction network to display bifurcations associated with these phenomena. The advantage of these conditions is that they impose fewer algebraic conditions on model parameters than conditions associated with standard bifurcation theorems. To derive the new conditions, a coordinate transformation will be made that will guarantee the existence of branches of positive equilibria in the system. This is particularly useful in mathematical biology, where only positive variable values are considered to be meaningful. The first part of the paper will be an extended introduction to SNA and algebraic geometry-related methods which are used in the coordinate transformation and set up of the theorems. In the second part of the paper we will focus on the derivation of bifurcation conditions using SNA and algebraic geometry. Conditions will be derived for three bifurcations: the saddle-node bifurcation, a simple branching point, both linked to bistability, and a simple Hopf bifurcation. The latter is linked to oscillatory behaviour.

      My friend Walter Blackstock says that a fairly simple chemical reaction network is believed to govern the circadian cycle: the daily waking-sleeping cycle that many animals have. It would be interesting to study this mathematically and see if one could find a Hopf bifurcation lurking in it as one adjusts the reaction rates!

      I’m reading lots of books about Petri nets, and I’m proud to say that I now know what a ‘siphon’ is, so I can try to understand that paper you referred me to a while back:

      • Manoj Gopalkrishnan, Catalysis in reaction networks.

      Is there a preview option for the comments that I’m missing?

      Sorry, no. I fixed your HTML. That little blurb saying “You may use these HTML tags” is not a great guide to how HTML actually works. Apparently some people are reading that and trying to create links like this:

      <a href = “http://arxiv.org/abs/q-bio/0608019″ title = “A Petri Net approach to the study of persistence in chemical reaction networks”>

      But that doesn’t work! You gotta do this:

      <a href = “http://arxiv.org/abs/q-bio/0608019″>A Petri Net approach to the study of persistence in chemical reaction networks</a>

      • What sort of insights?

        Thanks for fixing the HTML, John.

        For starters, my Catalysis in reaction networks paper talks about viewing catalysts as switches whose presence and absence alters the network topology in a way that is not compensated by other reactions. My plan is to use this point of view to try to reverse-engineer the “input/output response” of some very simple reaction networks.

        so I can try to understand that paper you referred
        me to a while back:

        Don’t be modest, John, you found the paper yourself. :-)

        • John Baez says:

          Manoj wrote:

          Don’t be modest, John, you found the paper yourself. :-)

          Not modest, forgetful!

          Okay – thinking of catalysts as switches. Now that I understand chemical reaction networks a bit better, I’ll try your paper again with that in mind.

          By the way, to get really cute quotes in blog comments here, you write:

          <blockquote>
          This is a quote!
          </blockquote>

          which gives:

          This is a quote!

  15. Scott says:

    The discussion of chemical reactions and programming languages reminded me of some very thought-provoking papers I’ve encountered on “chemical programming”:

    http://users.minet.uni-jena.de/csb/prj/organic/

    http://portal.acm.org/citation.cfm?id=1706654

    http://www.biosys.uni-jena.de/Projects/DFG_+CHEMORG+I_III.html

    etc.

  16. Allowa says:

    How can we save the planet?

    Please, be precise, all we can save is humanity, or animals.
    Planet is not in danger, it will not be harmed. It’s only us. I don’t like the way ecologists say that we need to get altogether for the earth.. no, it’s not true. We must move from our daily thinking ways because our habits are threatened.

    Although, I’m quite concerned by all the stuff you post here, thank you for it.

    • Phil Henshaw says:

      Natural systems thrive without needing to continually expand their scale, but economies must do so for their temporal stability. Figure that out. That’s what would save the earth.

      It’s really interesting in the world’s best data from 1970 shows that the relative rates of GDP, energy and CO2 production have remained completely constant. That indicates that the economy has a logic as a physical system of its own. It also means that the initial concept for how to use new kinds of growth to decouple energy and carbon from it is a complete and total failure, not showing the least bit of effect of any kind.

      It’s not so mysterious to people who study economies as behavioral systems rather than theoretical systems, but the difference isn’t mathematical so needs to be discussed in another forum.

  17. I already told you about Petri nets, which are popular in computer science… but also nice for describing chemical reactions […]

  18. […] the science of waiting in line. If you’re a faithful reader of this blog, you’ve already seen an example of a Petri net taken from […]

  19. Alex Nelson says:

    These fancy Petri networks seem to be a variation of the Chu Space theme…that may give a nice topological twist to things.

  20. Domingo Salazar says:

    Dear John,

    Myself and some friends are interested in the analogies between random walks and electrical networks. We are familiar with the descriptions of resitors and voltages in terms of absorbing random walks but we would like to see similar analogies for capacitors and inductors, but we have not found (or being able to create ourselves) any yet. You mentioned here that you were working on something like that. I would appreciate it if you would point out an appropriate reference.

    Also, the way the analogy works for a network of resistors requires a source and a sink while for a network of capacitors we are thinking of a closed system where a unit of charge is injected and a dynamical process unforlded until that charge is distributed amond all the capacitors. Would then the same interpretation of a resistor and voltage still apply?

You can use HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,869 other followers