These are the kinds of questions \u2013 though not literally \u2013 that fascinate Professor Wojciech Czerwi\u0144ski 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 \u2013 mathematical models of systems in which many processes occur simultaneously \u2013 and explains why a seemingly simple question about system behavior can lead to problems involving numbers beyond ordinary human comprehension.<\/p>\n\n\n\n
UW Science Daily: <\/strong>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?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: <\/strong>My research is in a branch of theoretical computer science called automata theory. An automaton is a model of computation \u2013 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n UW Science Daily:<\/strong> 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?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: <\/strong>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.<\/p>\n\n\n\n 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 \u2013 though only in a very specific way.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n UW Science Daily:<\/strong> But this isn\u2019t the same Petri as the Petri dish, right?<\/strong><\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: No, it\u2019s just a coincidence of names. The Petri associated with Petri nets was a 20th-century computer scientist\u2014or more precisely, a mathematician\u2014who died in 2010.<\/p>\n\n\n\n The Petri associated with Petri dishes was a 19th-century chemist who died in 1921.<\/p>\n\n\n\n An interesting side note is that Carl Adam Petri, the computer scientist, reportedly began his career working in a chemistry laboratory.<\/p>\n\n\n\n UW Science Daily: <\/strong>In your work, do the coordinates of that vector correspond to programs running in parallel?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: <\/strong>Exactly. We have a certain number of programs of the first type \u2013 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n UW Science Daily: <\/strong>This leads us to the striking result from your first ERC grant on the complexity of reachability. What did you manage to establish?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: <\/strong>Initially, researchers knew both lower and upper bounds for the problem\u2019s 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 \u2013 truly gigantic.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n The second result pushed the lower bound further \u2013 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.<\/p>\n\n\n\n UW Science Daily: Why study questions that might seem so impractical \u2013 and does it really matter whether the complexity is Ackermannian instead of exponential?<\/strong><\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: 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 \u201cunder the hood.\u201d<\/p>\n\n\n\n UW Science Daily: <\/strong>That sounds closer to mathematics than to computer science.<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: Yes. People tend to associate computer science and computational complexity with whether an application runs quickly or slowly on an ordinary person\u2019s computer.<\/p>\n\n\n\n We study things at a much more abstract level \u2013 objects and structures that are beautiful in their own right. Not everything needs an immediate practical application.<\/p>\n\n\n\n UW Science Daily: <\/strong>So in a sense, you work in mathematics\u2014the \u201cqueen of sciences\u201d\u2014but within the framework of its younger sister, computer science?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: Yes. Theoretical computer science is essentially mathematics. It is the mathematics of computation and processes. For some reason, it is classified as computer science.<\/p>\n\n\n\n The same thing happened with computer science logic. Logic was originally a branch of mathematics but gradually became part of computer science as well.<\/p>\n\n\n\n UW Science Daily: <\/strong>This year you received another ERC grant, a Consolidator Grant, to continue your research on reachability. The project is called POLARIS \u2013 what\u2019s the story behind the name?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: I like looking at the stars. You could also say that in my scientific work I deal with \u201cnavigating\u201d from one state to another. Polaris \u2013 the North Star \u2013 has helped people find their way for centuries, which is where the name comes from.<\/p>\n\n\n\n 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\u2019s 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 \u2013 and it was that star that effectively pointed north.<\/p>\n\n\n\n UW Science Daily: In the POLARIS project, are you continuing your work on reachability?<\/strong><\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: Yes, because determining the overall complexity does not close the story. It is natural to ask about special cases \u2013 for example, in dimension three.<\/p>\n\n\n\n We also want to understand how \u201cstructured\u201d the state space is, what hidden structures exist in these infinite graphs, and why the reachability problem has such an enormous level of complexity.<\/p>\n\n\n\n UW Science Daily: <\/strong>ERC grants are both prestigious and financially significant. The University of Warsaw also offers funding through the \u201cExcellence Initiative \u2013 Research University\u201d (IDUB) program. Have you had a chance to benefit from it as well?<\/p>\n\n\n\n Prof. Wojciech Czerwi\u0144ski: 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n A VASS can essentially be seen as a particular form of a Petri net \u2013 in fact, it is fundamentally equivalent to the general Petri net model.<\/p>\n\n\n\n Thank you for speaking with us.<\/strong><\/p>\n\n\n\n \u201cResearch University: Five questions for\u2026\u201d 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 \u2013 Research University (IDUB) program.<\/em><\/p>\n\n\n\n