Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów

 

Bisimulation Finiteness of Pushdown Systems Is Elementary (joint work with Stefan Göller)


Prelegent: Paweł Parys

2020-01-08 14:15

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.