For ancient civilisations, the night sky was an invaluable guide and navigational tool. POLARIS – a project by Prof. Wojciech Czerwiński, named after the North Star – will bring the researcher from the Faculty of Mathematics, Informatics and Mechanics at the University of Warsaw closer to solving one of the key dilemmas in computer science, namely the limits of achievability in systems with an infinite number of states. The scientist has become a laureate of a Consolidator Grant awarded by the European Research Council.

Prof. Wojciech Czerwiński won his first ERC grant five years ago, as a doctoral candidate. He is now an associate professor and one of ten representatives of the Faculty of Mathematics, Informatics and Mechanics among the winners of this prestigious contest. 

He continually asks challenging questions about reachability in infinite systems – that is, as he explains, in those models of programmes characterised by an infinite number of possible states.

This time, inspiration came from the night sky – observing it is one of the professor’s private hobbies. POLARIS, the project’s acronym, refers to the Pole Star. This extraordinary celestial body has been one of the best navigational tools since antiquity.

Each of us navigates almost every day. We check, for example, how to get from point A to point B in a crowded city in the simplest and quickest way. Prof. Wojciech Czerwiński tackles similar dilemmas, albeit in computer programmes, studying the movements and procedures that influence how they function.

„I am focused on seeking techniques that allow the reachability problem to be solved as quickly and simply as possible. It is a key factor in improving our understanding of how programmes operate,”says Prof. Czerwiński.

The researcher works on computational models known as state-based systems – especially infinite-state ones. The bulk of his project concerns determining whether it is possible to devise an algorithm faster than existing ones that allows a given programme to move from its initial situation to its final one.

Fast, faster, the fastest

What kinds of systems are involved? „When I talk about a system, I mean a computational model capable of representing many types of resources. Among them are, for example, Petri nets or VAS – Vector Addition Systems. For simplicity, you can imagine that these resources are apples, pears and plums. In practice, they may be chemical substances or, in computer science, various computer programmes. Returning to the simplified example: imagine that at the outset the system contains five apples, five plums and five pears. We can perform various kinds of moves: add two apples, or remove one apple, one pear and one plum. Or convert three apples into three plums. We have several such moves at our disposal. The question is whether we can eventually reach a state with 11 apples, 11 pears and 11 plums, starting from the five of each,” explains Prof. Czerwiński.

At first glance, the reachability problem appears simple, yet in reality it remains difficult and far from straightforward. Where is the limit of maximal speed? Over the next five years, the POLARIS team led by Prof. Wojciech Czerwiński will seek an answer.