Universality problem for unambiguous Vector Addition Systems with States

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

Uniwersytet Warszawski

Termin

22 kwietnia 2020 14:15

Informacje na temat wydarzenia

Online seminar

Tytuł w języku angielskim

joint work with Diego Figueira and Piotr Hofman

Seminarium

Seminarium „Teoria automatów”

---

I will show that the universality problem is ExpSpace-complete for unambiguous VASS,

which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS.

I also plan to present some more results concerning the interplay between unambiguity and VASS.

---