New pumping technique for 2-dimensional VASS

Prelegent(ci)

Radosław Piórkowski

Afiliacja

Uniwersytet Warszawski

Termin

5 czerwca 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

I will show that every run of 2-VASS allows some kind of pumping:
in some cases just a straightforward adaptation of 1D pumping techniques is enough —such runs we call 'thin'.

I will prove that if a run is not thin, it is 'thick' — has some nice geometric properties that enable a reasonable form of 2D pumping.

I will use this characterisation to reprove the exponential bound on the length of shortest accepting run.

---