New pumping technique for 2-dimensional VASS

Speaker(s)

Radosław Piórkowski

Affiliation

Uniwersytet Warszawski

Date

June 5, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---