A more individual-oriented, new version of Petri net solves a Computer Science problem which had troubled computer scientists for decades.

The coronavirus pandemic led many to become amateur mathematicians, as they sought to understand the rate at which hospitalized patients were rising and when herd immunity would be achieved. Even professional mathematicians were challenged by the task. A researcher at the University of Copenhagen was inspired to solve a decades-old problem in computer science and their breakthrough has been published in the Journal of the ACM.

“Like many others, I was out to calculate how the epidemic would develop. I wanted to investigate certain ideas from theoretical computer science in this context. However, I realized that the lack of solution to the old problem was a showstopper,” remarks Joachim Kock.

His approach to the issue has applications in epidemiology, computer science, and maybe other domains. A characteristic shared by these disciplines is the existence of systems in which the different components exert reciprocal effect. For example, if a healthy person encounters a person sick with COVID, two persons may get infected.

German teen comes up with clever solution

Understanding the breakthrough requires familiarity with the fact that such complicated systems may be expressed mathematically using so-called Petri nets. Carl Adam Petri, a German who was just 13 at the time, developed the technique in 1939 for use in chemistry. When two chemical compounds combine and react, it is possible that the same thing will take place as when an unaffected person comes into contact with an infected individual who has COVID.

In a Petri net, the different parts are drawn as circles, while events like a chemical reaction or an infection are drawn as squares. Next, arrows connecting circles and squares demonstrate the system’s interdependencies.

A very simple Petri net for COVID infection. The process starts with a person who is not infected. S stands for “susceptible.” Two people get infected as a result of contact with an infected individual (“I”). Later, something else will happen that will take someone out of the group of people who are infected. “R” stands for “recovered” in this context, which might mean either being healed or dead. The individual would no longer be a part of the afflicted group in either case.

The problem was considered unsolvable by computer scientists

Petri nets are used in chemistry to predict how the concentrations of different chemicals in a combination will change over time. This line of reasoning has impacted the usage of Petri nets in other disciplines, such as epidemiology: initially, there is a high “concentration” of healthy individuals, and as time goes on, the “concentration” of infected individuals rises. The usage of Petri nets in computer science is considerably different since individuals are prioritized over concentrations and growth occurs in stages rather than continually.

Joachim Kock wanted to use computer science’s more individual-focused Petri nets for COVID calculations. At this point, he ran into the same old problem:

“Basically, the processes in a Petri net can be described through two separate approaches. The first approach regards a process as a series of events, while the second approach sees the net as a graphical expression of the interdependencies between components and events,” explains Joachim Kock, highlighting:

“The serial approach is well suited for performing calculations. However, it has a downside since it describes causalities less accurately than the graphical approach. Further, the serial approach tends to fall short when dealing with events that take place simultaneously.”

“The problem was that nobody had been able to unify the two approaches. The computer scientists had more or less resigned, regarding the problem as unsolvable. This was because no-one had realized that you need to go all the way back and revise the very definition of a Petri net,” adds Joachim Kock.

Small changes may have a big effect.

The Danish mathematician saw that the issue might be resolved by making a little change to the concept of a Petri net:

“By allowing parallel arrows rather than just counting them and writing a number, additional information is made available. Things work out and the two approaches can be unified.”

The exact math behind why this extra information is important is hard to explain, but an analogy can help:

“Assigning numbers to objects has helped humanity greatly. For instance, it is highly practical that I can arrange the right number of chairs in advance for a dinner party instead of having to experiment with different combinations of chairs and guests after they have arrived. However, the number of chairs and guests does not reveal who will be sitting where. Some information is lost when we consider numbers instead of the real objects.”

Similar information is lost when the Petri net’s individual arrows are changed to numbers.

The benefits of both ways may be acquired at the same time by combining the two approaches, which requires a little more work to handle the parallel arrows separately but is handsomely rewarded.

The COVID circle has been closed.

Joachim Kock says the method improves our mathematical knowledge of complicated systems with numerous interdependencies but won’t affect computer scientists’ Petri net work:

“This is because the necessary modifications are mostly back-compatible and can be applied without need for revision of the entire Petri net theory.”

“Somewhat surprisingly, some epidemiologists have started using the revised Petri nets. So, one might say the circle has been closed!”

Joachim Kock sees another angle to the story:

“I wasn’t out to find a solution to the old problem in computer science at all. I just wanted to do COVID calculations. This was a bit like looking for your pen but realizing that you must find your glasses first. So, I would like to take the opportunity to advocate the importance of research which does not have a predefined goal. Sometimes research driven by curiosity will lead to breakthroughs.”

Source: 10.1145/3559103

Image Credit: Getty