Nie jesteś zalogowany | Zaloguj się

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.