New pumping technique for 2-dimensional VASS

DOI10.4230/LIPICS.MFCS.2019.62MaRDI QIDQ5092425FDOQ5092425

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

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

zbMATH Keywords

decidabilitypumpingvector addition systems with states

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Dimension-minimality and primality of counter nets
• Coverability in 2-VASS with one unary counter is in NP

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)