New Pumping Technique for 2-dimensional VASS
New Pumping Technique for 2-dimensional VASS
复制标题
二维 VASS 的新泵浦技术
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Radoslaw Piórkowski
中科院分区：
文献类型：
--
作者：
Wojciech Czerwinski;S. Lasota;Christof Löding;Radoslaw Piórkowski
我们提出了一个新的泵技术的2维矢量加法系统的状态（2-VASS）建设自然的几何性质的运行。我们通过重新证明最短接受运行长度的指数界，并通过证明2-VASS语言的一个新的泵引理来说明其适用性。该技术预计将有助于解决有关2-VASS语言的问题，例如，用于建立规则可分性问题的可判定性状态。
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.