2026-07-23T08:19:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11006 2024-03-06T10:47:02Z ddc:004 open_access

New Pumping Technique for 2-Dimensional VASS Czerwiński, Wojciech Lasota, Sławomir Löding, Christof Piórkowski, Radosław vector addition systems with states pumping decidability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Sławomir Lasota and Christof Löding and Radosław Piórkowski 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.62 urn:nbn:de:0030-drops-110066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.62 eng https://creativecommons.org/licenses/by/3.0/legalcode