These are the kinds of questions – though not literally – that fascinate Professor Wojciech Czerwiński of the University of Warsaw, recipient of two prestigious European Research Council (ERC) grants. In a conversation with UW Science Daily, he talks about Petri nets – mathematical models of systems in which many processes occur simultaneously – and explains why a seemingly simple question about system behavior can lead to problems involving numbers beyond ordinary human comprehension.
UW Science Daily: Six years ago, you received a prestigious ERC Starting Grant for research on infinite-state systems. What exactly are infinite-state systems, and what questions were you trying to answer?
Prof. Wojciech Czerwiński: My research is in a branch of theoretical computer science called automata theory. An automaton is a model of computation – a mathematical abstraction used to describe how a system performs computations. A classic example is the Turing machine, which serves as the fundamental model for studying the power and limitations of algorithms. In simple terms, a Turing machine is a model of a computer program.
This naturally raises a deeper question: what exactly is a model? Put simply, it is a simplified description of reality, a phenomenon, or a system. Physicists build models of the Universe and of atomic behavior. Although these models are not perfectly accurate descriptions of reality, they provide useful approximations that help explain how atoms, galaxies, weather systems, or genetic inheritance work.
Similarly, computer scientists construct models of what a program can do. And when certain processes occur in parallel rather than in a fixed order, a Petri net is used as a model of such a system.
UW Science Daily: Petri nets show up quite often in your work, from your ERC grant to your award-winning paper. Could you briefly explain what they are?
Prof. Wojciech Czerwiński: A Petri net is a model of a system in which events occur simultaneously rather than one after another. Concurrent software systems are a good example.
Mathematically, the state of such a system is described using a multidimensional vector, where each coordinate represents the number of elements with a given property present in the system at a particular moment. Because events happen concurrently, a single transition can change more than one coordinate – though only in a very specific way.
Carl Adam Petri was inspired by chemical reactions. He wanted to describe reactions that occur in parallel rather than as a chain of sequential steps.
UW Science Daily: But this isn’t the same Petri as the Petri dish, right?
Prof. Wojciech Czerwiński: No, it’s just a coincidence of names. The Petri associated with Petri nets was a 20th-century computer scientist—or more precisely, a mathematician—who died in 2010.
The Petri associated with Petri dishes was a 19th-century chemist who died in 1921.
An interesting side note is that Carl Adam Petri, the computer scientist, reportedly began his career working in a chemistry laboratory.
UW Science Daily: In your work, do the coordinates of that vector correspond to programs running in parallel?
Prof. Wojciech Czerwiński: Exactly. We have a certain number of programs of the first type – this is represented by the first coordinate of the vector. The second coordinate gives the number of programs of the second type, and so on. These programs run in parallel and can communicate with one another. This gives rise to what we call an infinite-state model, because there can be arbitrarily many possible configurations.
The problem I studied asks whether, starting from a given initial state and following a specified set of transitions, it is possible to reach a target state. This is the reachability problem.
It is very easy to state. Since the 1980s, it has been known that reachability is decidable, but for nearly half a century its exact computational complexity remained unknown. In other words, we did not know how much time or memory is required to decide whether a desired state can be reached.
UW Science Daily: This leads us to the striking result from your first ERC grant on the complexity of reachability. What did you manage to establish?
Prof. Wojciech Czerwiński: Initially, researchers knew both lower and upper bounds for the problem’s complexity. The lower bound was exponential space, meaning that the amount of memory required grows exponentially with the size of the input. The upper bound, on the other hand, was so-called Ackermannian complexity. It is enormous – truly gigantic.
The first major result was raising the lower bound to what we call a tower of twos. Typically, a tower of twos means 2 raised to the power of 2, raised to the power of 2, and so on, repeated n times. That is already an extraordinarily large complexity class, and the Ackermann function grows even faster.
The second result pushed the lower bound further – from the tower of twos all the way up to the Ackermann level. As a result, we proved that the computational complexity of the reachability problem is Ackermannian.
UW Science Daily: Why study questions that might seem so impractical – and does it really matter whether the complexity is Ackermannian instead of exponential?
Prof. Wojciech Czerwiński: At its core, this is a mathematical question. We wanted to understand the structures governing the algorithm. Knowing its complexity reveals a great deal about its nature. It also encourages us to develop the right concepts and terminology for describing these phenomena and to understand what is happening “under the hood.”
UW Science Daily: That sounds closer to mathematics than to computer science.
Prof. Wojciech Czerwiński: Yes. People tend to associate computer science and computational complexity with whether an application runs quickly or slowly on an ordinary person’s computer.
We study things at a much more abstract level – objects and structures that are beautiful in their own right. Not everything needs an immediate practical application.
UW Science Daily: So in a sense, you work in mathematics—the “queen of sciences”—but within the framework of its younger sister, computer science?
Prof. Wojciech Czerwiński: Yes. Theoretical computer science is essentially mathematics. It is the mathematics of computation and processes. For some reason, it is classified as computer science.
The same thing happened with computer science logic. Logic was originally a branch of mathematics but gradually became part of computer science as well.
UW Science Daily: This year you received another ERC grant, a Consolidator Grant, to continue your research on reachability. The project is called POLARIS – what’s the story behind the name?
Prof. Wojciech Czerwiński: I like looking at the stars. You could also say that in my scientific work I deal with “navigating” from one state to another. Polaris – the North Star – has helped people find their way for centuries, which is where the name comes from.
As a side note, the North Star has not always been as precise a reference point as it is today. Ancient sailors had to rely on a different star to determine north. This is due to the slow shift of Earth’s rotational axis, which means that the north celestial pole moves against the background of the stars. As a result, a few thousand years ago another star was actually closer to the pole – and it was that star that effectively pointed north.
UW Science Daily: In the POLARIS project, are you continuing your work on reachability?
Prof. Wojciech Czerwiński: Yes, because determining the overall complexity does not close the story. It is natural to ask about special cases – for example, in dimension three.
We also want to understand how “structured” the state space is, what hidden structures exist in these infinite graphs, and why the reachability problem has such an enormous level of complexity.
UW Science Daily: ERC grants are both prestigious and financially significant. The University of Warsaw also offers funding through the “Excellence Initiative – Research University” (IDUB) program. Have you had a chance to benefit from it as well?
Prof. Wojciech Czerwiński: I am employed through a European grant, but one member of my team, Henry Sinclair-Banks, a postdoctoral researcher from the University of Warwick, organized the SAMSA workshop with support from the IDUB program.
Workshops focused on a narrower topic are extremely valuable. Conferences bring together researchers from a broader field and help us get a sense of what is happening across the discipline as a whole. Workshops, on the other hand, make it easier to meet people working on closely related problems, and they often lead to new research collaborations.
Henry spent more than a year in Warsaw as a postdoctoral researcher. Together, we wrote several papers, including work on the reachability problem in VASS models with additional integer counters, as well as reachability in certain classes of VASS systems with very specific structural properties.
A VASS can essentially be seen as a particular form of a Petri net – in fact, it is fundamentally equivalent to the general Petri net model.
Thank you for speaking with us.
“Research University: Five questions for…” is a series of interviews with researchers at the University of Warsaw who have carried out their projects within the framework of the Initiative of Excellence – Research University (IDUB) program.
The text was originally published in Polish on the Serwis Naukowy UW website on June 16, 2026.
