siiky
2022/06/23
2022/07/23
en
Unfortunately there are no uppercase subscript letters? When you see "_N" imagine "N" is in subscript. And I'm actually finishing writing this almost exactly one month later... :/ Some details of what I thought at the time escape me.
Finished reading Ch. 3 & 4 some weeks ago.
On Ch. 3 there wasn't that much new to me -- notation was slightly different from what I was used to, but in general it wasn't complicated to follow. There was terminology I didn't remember too, but mostly just had to go back and read my notes from University.
Ch. 4, however, was an interesting one. They define two categories: one of Petri nets (called Petri), and another of Petri net executions.
with nets as objects; and another of Petri net executions of a given net (called F(N), with some Petri net N, and a fancy calligraphic F), with markings as objects, and transitions as morphisms.
The category of Petri nets as nets as objects (obviously), and morphisms are... weird.
A morphism N → M of the category Petri is a pair 〈f, g〉 where:
Additionally, these morphisms must preserve a couple of properties:
I can't explain these in words right now, so... exercise for the reader!
But I'll try anyway with an example: suppose that f transforms transitions in such a way that they consume and produce double the amount of tokens, and that g doubles the amount of tokens of each place; then, if a particular place p of the net N has 2 tokens, and a transition t of the net N that consumes 2 tokens from p, there's an "equivalent" place p in the net M with 4 tokens, and an "equivalent" transition t in the net M that consumes 4 tokens from p.
Altogether, I think these form a sort of super/subnet relation between nets, that visually looks a lot like super/subgraphs.
The category Petri can be restricted to a subcategory (Petri_G), which is the one used in practice, but I think the details aren't relevant for this post (it has to do with the g, if you wish to know).
The possible executions of a given net form also a category if you take the markings as objects and the transitions as morphisms.
Markings are represented as products of places. For example, if your net has places p1 and p2, a marking of 3 tokens in p1 and 2 tokens in p2 could be represented as p1·p1·p1·p2·p2. This representation isn't unique (and cannot be unique due to math reasons), since · is commutative -- p2·p1·p2·p1·p1 is another possible representation of the same marking.
In the formal definition of Petri nets, a token is a token, no matter if it was produced before or after another token in the same place. In other words, tokens of a place are indistinguishable from each other. However, when programming, it usually matters what the value of a thing is. In general, a function applied to two different values will compute two different values as well.
Magics of mathematics to the rescue! You can visualize the evolution of a net as a string diagram! Really cool.
ACT 2020 Tutorial: Introduction to string diagrams (Fabrizio Genovese)
And even cooler because it brings an important detail in. Tokens in this graphical representation are not confused with each other: there's clearly a string (hence the name) connecting a certain value in a certain point in time to all its "ancestors", i.e., the order of firings and which tokens were consumed and produced to result in that value.
And even cooler cooler is that, while you can now tell tokens apart, nobody tells you what order they have to be consumed in! This may or may not be something useful, but I think it's a neat detail to keep in mind. An implementation may provide different "token choosing" abilities: queues, stacks, sets (random), with or without priorities (e.g. you may want to always consume the smallest integer of a place), &c.
About this time I started wondering... Are there Petri net implementations? What are they used for, modeling or programming? Strictly graphical or textual? Easy to work with? VCS-friendly?
Statebox supposedly had a prototype implementation that is no more. At least I can't find it anymore and the people that I know knew about it don't know about it no more either. I think they're working on something new, but not publicly.
So wondering I continued, thinking of a possible language. I don't have anything concrete yet