ERC grant
Starting from March 2021 I am the PI of an ERC Starting grant INFSYS (Challenging Problems in Infinite-State Systems). The three main goals of the project are to understand better:
- the reachability problem for Vector Addition Systems and its extensions
- the separability problem for various kinds of automata
- the structure of unambiguous systems
Hermitage workshops
In order to inspire research atmosphere we organize a sequence of small workshops. During each such a workshop for around one week we aim at leaving all the other important projects away and focus on a few concrete research problems. Our experience shows that this kind of meetings are often scientifically and socially very fruitful.
Hermitage Workshop II (16.05.2022 - 20.05.2022)
Location: Tyniec near Kraków, Poland, Benedictine abbey in Tyniec
Plan:
Arrival: Sunday 22:00, Departure: Friday 16:30
Program of each day:
| 8:00 - 8:30 | Breakfast |
| 9:00 - 13:00 | Discussion and problem solving |
| 13:00 - 14:00 | Lunch |
| 14:00 - 18:00 | Discussion and problem solving |
| 18:00 - 19:00 | Dinner |
| 19:00 - ∞ | Discussion and free time |
Participants:
- Hector Buffiere
- Agnishom Chattopadhyay
- Tien Chu
- Lorenzo Clemente
- Wojciech Czerwiński
- Arka Ghosh
- Roland Guttenberg
- Ismaël Jecker
- Filip Mazowiecki
- Radosław Piórkowski
- David Purser
- Miron Szewczyk
Research problems considered:
- For VAS V and its configuration c let Reach(V, c) be the set of configurations reachable in V from c. We know that in general equality of reachability sets is undecidable, but it seems that in the case when V1 is reverse of V2 we can decide whether Reach(V1, c1) ⊆ Reach(V2, c2) for any c1, c2. The question is what are the conditions for V1 and V2 for this problem to be decidable.
- Two systems S1 and S2 are multiplicity-equivalent if each word has the same number of accepting runs in S1 and S2.
We consider the decidability question for the multiplicity-equivalence of
- Parikh automata (equivalently integer VASSes)
- One counter Nets (one dimensional VASSes)
Hermitage Workshop I (21.03.2022 - 25.03.2022)
Location: Chęciny, Poland, European Centre of Geological Education
Plan:
Arrival: Sunday 22:00, Departure: Friday 16:30
Program of each day:
| 9:00 - 10:00 | Breakfast |
| 10:00 - 14:00 | Discussion and problem solving |
| 14:00 - 15:00 | Lunch |
| 15:00 - 19:30 | Discussion and problem solving |
| 19:30 - 20:30 | Dinner |
| 20:30 - ∞ | Discussion and free time |
Participants:
- Hector Buffiere
- Lorenzo Clemente
- Wojciech Czerwiński
- Arka Ghosh
- Piotr Hofman
- Ismaël Jecker
Research problems considered:
- Given monoid M, decide whether it is decomposable in the following sense: M is decomposable into M1, M2, ..., Mk if M is a submonoid of M1 x M2 x ... x Mk. A special case is when M is a group is also an interesting question.
- Two systems S1 and S2 are multiplicity-equivalent if each word has the same number of accepting runs in S1 and S2.
We consider the decidability question for the multiplicity-equivalence of
- Parikh automata (equivalently integer VASSes)
- One counter Nets (one dimensional VASSes)