New pumping technique for 2-dimensional VASS

DOI10.4230/LIPICS.MFCS.2019.62MaRDI QIDQ5092425zbMATH OpenFDO

Authors Wojciech Czerwiński, Sławomir Lasota, Christof Löding, Radosław Piórkowski

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1906.10494

zbMATH Keywords

decidabilitypumpingvector addition systems with states

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• CONCUR 2004 - Concurrency Theory
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States
• scientific article; zbMATH DE number 1759422

Cites work

• Langages à un compteur
• On the reachability problem for 5-dimensional vector addition systems
• Parallel program schemata
• Reachability in two-dimensional unary vector addition systems with states is NL-complete
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Regular separability of one counter automata
• The complexity of regular abstractions of one-counter languages
• The taming of the semi-linear set

Cited in

(3)

• Coverability in 2-VASS with one unary counter is in NP
• scientific article; zbMATH DE number 7559493 (Why is no real title available?)
• Dimension-minimality and primality of counter nets

This page was built for publication: New pumping technique for 2-dimensional VASS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092425)