8 ms·

Petri Nets Are Monoids (1990) [pdf]

72 points by boshomi 7y ago

ampdepolymerase 7y ago
For those who are interested, Petri nets have a lot of applications in CS, for example, spiking neural networks.
adamnemecek 7y ago
They can also be reasoned about in terms of linear logic. https://www.researchgate.net/publication/318253097_Petri_Nets_as_Models_of_Linear_Logic https://www.researchgate.net/publication/318253097_Petri_Net...
stebann 7y ago
They can be used for modelling actions and states, including the tricky cases where an automaton would become too complex.
- kitd 7y ago
  Indeed. Finite state machines are a subset of Petri nets, having deterministic state transitions. Petri nets are useful where concurrent state transitions needs to be modelled, and are thus useful when modelling the physical world.
  - stebann 7y ago
    Thanks. I forgot to appoint that.
yingw787 7y ago
For those who don’t know what a monoid is, like me three months ago, I believe a monoid is something that implements monoidal operations, which are binary associative operations with an identity. Integers have monoidal operations like addition and multiplication. You have two arguments, which don’t matter in ordering, and where an identity like the additive or multiplicative identity exists.
- kragen 7y ago
  This is all correct! Except for order not mattering, which is true of your examples but not true in general. But integer addition and multiplication also have a variety of other interesting algebraic properties: they are invertible (except multiplication by 0) and commutative, one distributes over the other, and integer addition has inverse elements. Some other monoids may give the flavor more clearly: - string concatenation is a monoid, with the empty string as the identity element. In fact, string concatenation is the most general monoid on a set, called the "free monoid"; all other monoids can be made from it by defining a canonicalization operation. For integer addition, for example, you can collapse a string of integers such as [4, -1, 2] down to their sum, such as [5]. Note that the free monoid is not commutative, and although it is invertible (in "hairy" || " and a half" = "hairy and a half", you can take " and a half" off and get the original "hairy"), it doesn't have inverse elements. - max and min on a closed set, and more generally all semilattices. Let's write 4 \/ 5 = 5 \/ 4 = 5. This \/ is associative and has an identity (whatever the maximum of the closed set is; we can augment the integers with -∞ and +∞ and use -∞ as the identity element), so it forms a monoid. Any theorem about monoids will work equally well for string concatenation and for this pairwise max operator. Isn't that wild? - & and | for bitstrings of some length. This is also a lattice. - Matrix multiplication (for matrices of a particular square shape). - The morphological dilation operation.
  - techbio 7y ago
    Fascinating. Curious about matrix multiplication and a “particular square shape”. I’m interested if you would care to elaborate on the matrix relationship.
    - kragen 7y ago
      Oh, well, I mean that if you have a 3×3 matrix and a 4×4 matrix, you can't even multiply them. So 4×4 matrices form a monoid under multiplication, as do 3×3 matrices, but matrices in general do not. It turns out that they actually form a much richer structure called a ring when you add in their addition operator as well: https://en.m.wikipedia.org/wiki/Matrix_ring https://en.m.wikipedia.org/wiki/Matrix_ring
hobbio 7y ago
Paged through the article for pictures, but the only example with tensors was trivial. Could anyone who read the thing tell if there's an intuitive explanation of the binary operation on full nets?

72 points by boshomi 7y ago

For those who are interested, Petri nets have a lot of applications in CS, for example, spiking neural networks.

They can also be reasoned about in terms of linear logic. https://www.researchgate.net/publication/318253097_Petri_Nets_as_Models_of_Linear_Logic https://www.researchgate.net/publication/318253097_Petri_Net...

stebann 7y ago

They can be used for modelling actions and states, including the tricky cases where an automaton would become too complex.

kitd 7y ago
Indeed. Finite state machines are a subset of Petri nets, having deterministic state transitions. Petri nets are useful where concurrent state transitions needs to be modelled, and are thus useful when modelling the physical world.
- stebann 7y ago
  Thanks. I forgot to appoint that.

yingw787 7y ago

For those who don’t know what a monoid is, like me three months ago, I believe a monoid is something that implements monoidal operations, which are binary associative operations with an identity. Integers have monoidal operations like addition and multiplication. You have two arguments, which don’t matter in ordering, and where an identity like the additive or multiplicative identity exists.

kragen 7y ago
This is all correct! Except for order not mattering, which is true of your examples but not true in general. But integer addition and multiplication also have a variety of other interesting algebraic properties: they are invertible (except multiplication by 0) and commutative, one distributes over the other, and integer addition has inverse elements. Some other monoids may give the flavor more clearly: - string concatenation is a monoid, with the empty string as the identity element. In fact, string concatenation is the most general monoid on a set, called the "free monoid"; all other monoids can be made from it by defining a canonicalization operation. For integer addition, for example, you can collapse a string of integers such as [4, -1, 2] down to their sum, such as [5]. Note that the free monoid is not commutative, and although it is invertible (in "hairy" || " and a half" = "hairy and a half", you can take " and a half" off and get the original "hairy"), it doesn't have inverse elements. - max and min on a closed set, and more generally all semilattices. Let's write 4 \/ 5 = 5 \/ 4 = 5. This \/ is associative and has an identity (whatever the maximum of the closed set is; we can augment the integers with -∞ and +∞ and use -∞ as the identity element), so it forms a monoid. Any theorem about monoids will work equally well for string concatenation and for this pairwise max operator. Isn't that wild? - & and | for bitstrings of some length. This is also a lattice. - Matrix multiplication (for matrices of a particular square shape). - The morphological dilation operation.
- techbio 7y ago
  Fascinating. Curious about matrix multiplication and a “particular square shape”. I’m interested if you would care to elaborate on the matrix relationship.
  - kragen 7y ago
    Oh, well, I mean that if you have a 3×3 matrix and a 4×4 matrix, you can't even multiply them. So 4×4 matrices form a monoid under multiplication, as do 3×3 matrices, but matrices in general do not. It turns out that they actually form a much richer structure called a ring when you add in their addition operator as well: https://en.m.wikipedia.org/wiki/Matrix_ring https://en.m.wikipedia.org/wiki/Matrix_ring

hobbio 7y ago

Paged through the article for pictures, but the only example with tensors was trivial. Could anyone who read the thing tell if there's an intuitive explanation of the binary operation on full nets?