The reachability problem for two-dimensional vector addition systems with states

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...

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Blondin, M, Englert, M, Finkel, A, Göller, S, Haase, C, Lazic, R, McKenzie, P, Totzke, P
Định dạng:	Journal article
Ngôn ngữ:	English
Được phát hành:	Association for Computing Machinery 2021

Những quyển sách tương tự

Logics for Continuous Reachability in Petri Nets and Vector Addition Systems with States
Bằng: Haase, C, et al.
Được phát hành: (2017)

A polynomial-time algorithm for reachability in branching VASS in dimension one
Bằng: Göller, S, et al.
Được phát hành: (2016)

Directed reachability for infinite-state systems
Bằng: Blondin, M, et al.
Được phát hành: (2021)

Affine extensions of integer vector addition systems with states
Bằng: Blondin, M, et al.
Được phát hành: (2018)

Affine extensions of integer vector addition systems with states
Bằng: Blondin, M, et al.
Được phát hành: (2021)

Vector reachability problem in SL (2, ℤ)
Bằng: Potapov, I, et al.
Được phát hành: (2016)

Vector and scalar reachability problems in SL(2, Z)
Bằng: Potapov, I, et al.
Được phát hành: (2018)

On reachability problems for low-dimensional matrix semigroups
Bằng: Colcombet, T, et al.
Được phát hành: (2019)

Strategy complexity of reachability in countable stochastic 2-player games
Bằng: Kiefer, S, et al.
Được phát hành: (2024)

On the Relationship between Reachability Problems in Timed and Counter Automata
Bằng: Haase, C, et al.
Được phát hành: (2012)

On the relationship between reachability problems in timed and counter automata
Bằng: Haase, C, et al.
Được phát hành: (2012)

The logical view on continuous petri net
Bằng: Haase, CJ, et al.
Được phát hành: (2017)

On affine reachability problems
Bằng: Jaax, S, et al.
Được phát hành: (2020)

Reachability in Succinct and Parametric One−Counter Automata
Bằng: Haase, C, et al.
Được phát hành: (2009)

Reachability in Succinct and Parametric One-Counter Automata
Bằng: Haase, C, et al.
Được phát hành: (2009)

Reachability problems for linear dynamical systems
Bằng: Chonev, V
Được phát hành: (2015)

Reachability problems in nondeterministic polynomial maps on the integers
Bằng: Ko, SK, et al.
Được phát hành: (2018)

Reachability and escape problems in linear dynamical systems
Bằng: Dcosta, J
Được phát hành: (2024)

The pseudo-reachability problem for diagonalisable linear dynamical systems
Bằng: D'Costa, J, et al.
Được phát hành: (2022)

Functional Reachability
Bằng: Ong, C, et al.
Được phát hành: (2009)

Relating Data Independent Trace Checks in CSP with UNITY Reachability under a Normality Assumption
Bằng: Roscoe, A, et al.
Được phát hành: (2004)

TWO-DIMENSIONAL CONDUCTIVITY IN THE CONTACT REGIONS OF SILICON MOSFETS
Bằng: Kressrogers, E, et al.
Được phát hành: (1980)

A memory efficient reachability data structure through bit vector compression
Bằng: van Schaik, S, et al.
Được phát hành: (2011)

A memory efficient reachability data structure through bit vector compression.
Bằng: Schaik, S, et al.
Được phát hành: (2011)

Reachability in Stochastic Timed Games.
Bằng: Bouyer, P, et al.
Được phát hành: (2009)

Reachability Analysis for Annotated Code
Bằng: Janota, M, et al.
Được phát hành: (2007)

Revisiting reachability in timed automata
Bằng: Quaas, K, et al.
Được phát hành: (2017)

Expected Reachability−Time Games
Bằng: Forejt, V, et al.
Được phát hành: (2010)

Expected reachability-time games
Bằng: Forejt, V, et al.
Được phát hành: (2016)

Expected Reachability-Time Games.
Bằng: Forejt, V, et al.
Được phát hành: (2010)

Decision Problems for Petri Nets and Vector Addition Systems
Bằng: Hack, Michael
Được phát hành: (2023)

Reachability Analysis of Neural Feedback Loops
Bằng: Everett, Michael, et al.
Được phát hành: (2022)

Minimal Reachability is Hard to Approximate
Bằng: Jadbabaie, A, et al.
Được phát hành: (2023)

Reachability in pushdown register automata
Bằng: Murawski, A, et al.
Được phát hành: (2017)

Reachability−Time Games on Timed Automata
Bằng: Jurdzinski, M, et al.
Được phát hành: (2007)

Asymptotic orders of reachability in linear dynamic systems
Bằng: Özveren, Cüneyt M
Được phát hành: (2005)

Reachability and robust design in dynamic systems
Bằng: Harwood, Stuart Maxwell
Được phát hành: (2016)

Reachability in recursive Markov decision processes.
Bằng: Brázdil, T, et al.
Được phát hành: (2008)

Traversability, Reconfiguration, and Reachability in the Gadget Framework
Bằng: Ani, Joshua, et al.
Được phát hành: (2023)

Branching−Time Model Checking of Parametric One−Counter Automata
Bằng: Göller, S, et al.
Được phát hành: (2012)