You are not logged in | Log in

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.