Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete

Prelegent(ci)

Paweł Parys

Afiliacja

MIM UW

Termin

9 listopada 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

We consider the problem of deciding whether a given pushdown system all of whose ε-transitions are deterministic is weakly bisimulation finite, that is, whether it is weakly bisimulation equivalent to a finite system. We prove that this problem is 2-EXPTIME-complete. This consists of three elements: First, we prove that the smallest finite system that is weakly bisimulation equivalent to a fixed pushdown system, if exists, has size at most doubly exponential in the description size of the pushdown system. Second, we propose a fast algorithm deciding whether a given pushdown system is weakly bisimulation equivalent to a finite system of a given size. Third, we prove 2-EXPTIME-hardness of the problem. The problem was known to be decidable, but the previous algorithm had Ackermannian complexity (6-EXPSPACE in the easier case of pushdown systems without ε-transitions); concerning lower bounds, only EXPTIME-hardness was known. The talk is based on a paper accepted to SODA 2023, co-authored by Stefan Göller. It is a continuation of our previous paper (LICS 2020, presented on the seminar in January 2020), where we showed an 6-EXPSPACE algorithm solving the problem in the easier case of pushdown systems without ε-transitions.

---