The reachability problem for two-dimensional vector addition systems with states
We prove that the reachability problem for two-dimensional vector addition systems with states is NL-complete or PSPACE-complete, depending on whether the numbers in the input are encoded in unary or binary. As a key underlying technical result, we show that, if a configuration is reachable, then th...
| Үндсэн зохиолчид: | , , , , , , , |
|---|---|
| Формат: | Journal article |
| Хэл сонгох: | English |
| Хэвлэсэн: |
Association for Computing Machinery
2021
|