Dr. Wojciech Czerwiński from the UW Faculty of Mathematics, Informatics and Mechanics has received prestigious European Research Council grants. His team will analyse problems related to infinite state systems.

Is it possible to develop a faster algorithm answering the question about the reachability of a specific computer system? It is one of the questions asked by Dr. Wojciech Czerwiński from the UW Institute of Informatics.

UW researcher has been awarded prestigious European Research Council Starting Grant. ERC supports talented early-career scientists with 2-7 years of experience since completion of doctoral thesis.

Reachability questions

“There are many kinds of models. We have, for example, computational models called infinite-state systems,” says Dr. Wojciech Czerwiński from the Institute of Informatics at the UW Faculty of Mathematics, Informatics and Mechanics, whose project entitled “Challenging Problems in Infinite-State Systems” (INFSYS) was awarded the prestigious ERC Starting Grant ERC.

The author of the INFSYS project aims to present solutions to the greatest challenges arising in the field of infinite state systems. The project’s objectives concentrate on three main problems.

One of them is reachability in Petri nets and VAS systems (Vector Addition Systems). “The Petri Net is a model assuming the existence of several different resources. For the sake of simplicity, it can be said that these resources are apples, pears and plums. In practice, they can be, for example, chemicals or, in terms of computer science, various types of computer programs. But going back to the simplification, let’s imagine that at the beginning we have 5 apples, 5 plums and 5 pears in the system. We can make different types of movements: add 2 apples or take 1 apple, 1 pear and 1 plum. Or add 3 apples and 3 plums at once. We have several of these types of movements. The question is whether we can finally reach 11 apples, 11 pears and 11 plums out of these 5 apples, 5 plums and 5 pears,” explains Dr. Czerwiński.

The aim of the project is to create an algorithm that for a given system, defining the initial situation and the set of moves available, would answer the question about the possibility of transition to a specific end situation. “Such algorithms already exist, of course, but we are trying to create a faster one. Or prove that it is impossible to design faster. We are talking about a specific problem of reachability,” stresses Dr. Czerwiński.

The other two problems presented in the INFSYS project are separation in automata theory and unambiguity in simple models.