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...
| Váldodahkkit: | , , , , , , , |
|---|---|
| Materiálatiipa: | Journal article |
| Giella: | English |
| Almmustuhtton: |
Association for Computing Machinery
2021
|
| _version_ | 1826294319828434944 |
|---|---|
| author | Blondin, M Englert, M Finkel, A Göller, S Haase, C Lazic, R McKenzie, P Totzke, P |
| author_facet | Blondin, M Englert, M Finkel, A Göller, S Haase, C Lazic, R McKenzie, P Totzke, P |
| author_sort | Blondin, M |
| collection | OXFORD |
| description | 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 there exists a witnessing path whose sequence of transitions is contained in a bounded language defined by a regular expression of pseudo-polynomially bounded length. This, in turn, enables us to prove that the lengths of minimal reachability witnesses are pseudo-polynomially bounded.
|
| first_indexed | 2024-03-07T03:43:48Z |
| format | Journal article |
| id | oxford-uuid:bec2b10c-f6a7-404c-952d-85b901a57e12 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:43:48Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:bec2b10c-f6a7-404c-952d-85b901a57e122022-03-27T05:42:25ZThe reachability problem for two-dimensional vector addition systems with statesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:bec2b10c-f6a7-404c-952d-85b901a57e12EnglishSymplectic ElementsAssociation for Computing Machinery2021Blondin, MEnglert, MFinkel, AGöller, SHaase, CLazic, RMcKenzie, PTotzke, PWe 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 there exists a witnessing path whose sequence of transitions is contained in a bounded language defined by a regular expression of pseudo-polynomially bounded length. This, in turn, enables us to prove that the lengths of minimal reachability witnesses are pseudo-polynomially bounded. |
| spellingShingle | Blondin, M Englert, M Finkel, A Göller, S Haase, C Lazic, R McKenzie, P Totzke, P The reachability problem for two-dimensional vector addition systems with states |
| title | The reachability problem for two-dimensional vector addition systems with states |
| title_full | The reachability problem for two-dimensional vector addition systems with states |
| title_fullStr | The reachability problem for two-dimensional vector addition systems with states |
| title_full_unstemmed | The reachability problem for two-dimensional vector addition systems with states |
| title_short | The reachability problem for two-dimensional vector addition systems with states |
| title_sort | reachability problem for two dimensional vector addition systems with states |
| work_keys_str_mv | AT blondinm thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT englertm thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT finkela thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT gollers thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT haasec thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT lazicr thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT mckenziep thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT totzkep thereachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT blondinm reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT englertm reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT finkela reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT gollers reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT haasec reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT lazicr reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT mckenziep reachabilityproblemfortwodimensionalvectoradditionsystemswithstates AT totzkep reachabilityproblemfortwodimensionalvectoradditionsystemswithstates |