On affine reachability problems
We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent resul...
| Egile Nagusiak: | , |
|---|---|
| Formatua: | Conference item |
| Hizkuntza: | English |
| Argitaratua: |
Schloss Dagstuhl
2020
|