joint work with Stefan Göller

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Jan. 8, 2020, 2:15 p.m.

Room

room 5050

Title in Polish

Bisimulation Finiteness of Pushdown Systems Is Elementary

Seminar

Seminar Automata Theory

---

We show that in case a pushdown system is bisimulation equivalent to a finite system, then there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the pushdown system. As a consequence we obtain that it is elementarily decidable if a given pushdown system is bisimulation equivalent to some finite system. This improves a previously best-known Ackermann upper bound for this problem.

---