Coverability in 1-VASS with Disequality Tests
share
We show that the control-state reachability problem for one-dimensional vector addition systems with disequality tests is solvable in polynomial time. For the test-free case we moreover show that control-state reachability is in NC, i.e., solvable in polylogarithmic parallel time.
READ FULL TEXT