文章基本信息

标题：New Pumping Technique for 2-Dimensional VASS
本地全文：下载
作者：Wojciech Czerwinski ; Slawomir Lasota ; Christof L{"o}ding 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-14
DOI：10.4230/LIPIcs.MFCS.2019.62
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We propose a new pumping technique for 2-dimensional vector addition systems with states (2-VASS) building on natural geometric properties of runs. We illustrate its applicability by reproving an exponential bound on the length of the shortest accepting run, and by proving a new pumping lemma for languages of 2-VASS. The technique is expected to be useful for settling questions concerning languages of 2-VASS, e.g., for establishing decidability status of the regular separability problem.
关键词：vector addition systems with states; pumping; decidability