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

Bibliografske podrobnosti
Main Authors:	Blondin, M, Englert, M, Finkel, A, Göller, S, Haase, C, Lazic, R, McKenzie, P, Totzke, P
Format:	Journal article
Jezik:	English
Izdano:	Association for Computing Machinery 2021

Podobne knjige/članki

A polynomial-time algorithm for reachability in branching VASS in dimension one
od: Göller, S, et al.
Izdano: (2016)

Logics for Continuous Reachability in Petri Nets and Vector Addition Systems with States
od: Haase, C, et al.
Izdano: (2017)

The Complexity of Reachability in Affine Vector Addition Systems with States
od: Michael Blondin, et al.
Izdano: (2021-07-01)

Directed reachability for infinite-state systems
od: Blondin, M, et al.
Izdano: (2021)

Vector Addition System Reversible Reachability Problem
od: Jérôme Leroux
Izdano: (2013-02-01)

The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
od: leroux jerome
Izdano: (2010-09-01)

Vector reachability problem in SL (2, ℤ)
od: Potapov, I, et al.
Izdano: (2016)

Affine extensions of integer vector addition systems with states
od: Blondin, M, et al.
Izdano: (2018)

Strategy complexity of reachability in countable stochastic 2-player games
od: Kiefer, S, et al.
Izdano: (2024)

Bounded Reachability Problems are Decidable in FIFO Machines
od: Benedikt Bollig, et al.
Izdano: (2022-01-01)

Vector and scalar reachability problems in SL(2, Z)
od: Potapov, I, et al.
Izdano: (2018)

Affine extensions of integer vector addition systems with states
od: Blondin, M, et al.
Izdano: (2021)

On reachability problems for low-dimensional matrix semigroups
od: Colcombet, T, et al.
Izdano: (2019)

Affine Extensions of Integer Vector Addition Systems with States
od: Michael Blondin, et al.
Izdano: (2021-07-01)

On the Relationship between Reachability Problems in Timed and Counter Automata
od: Haase, C, et al.
Izdano: (2012)

On the relationship between reachability problems in timed and counter automata
od: Haase, C, et al.
Izdano: (2012)

Well Behaved Transition Systems
od: Michael Blondin, et al.
Izdano: (2017-09-01)

On affine reachability problems
od: Jaax, S, et al.
Izdano: (2020)

Link-Based Similarity Measures Using Reachability Vectors
od: Seok-Ho Yoon, et al.
Izdano: (2014-01-01)

Reachability in Succinct and Parametric One−Counter Automata
od: Haase, C, et al.
Izdano: (2009)

Reachability in Succinct and Parametric One-Counter Automata
od: Haase, C, et al.
Izdano: (2009)

The logical view on continuous petri net
od: Haase, CJ, et al.
Izdano: (2017)

Construction of the Reachable Set for a Two-Dimensional Bilinear Impulsive Control System
od: D. Apanovich, et al.
Izdano: (2016-03-01)

Reachability problems for linear dynamical systems
od: Chonev, V
Izdano: (2015)

Reachability and escape problems in linear dynamical systems
od: Dcosta, J
Izdano: (2024)

Reachability problems in nondeterministic polynomial maps on the integers
od: Ko, SK, et al.
Izdano: (2018)

Reachability Problem for Weak Multi-Pushdown Automata
od: Wojciech Czerwiński, et al.
Izdano: (2013-09-01)

The pseudo-reachability problem for diagonalisable linear dynamical systems
od: D'Costa, J, et al.
Izdano: (2022)

Functional Reachability
od: Ong, C, et al.
Izdano: (2009)

Reachability in Stochastic Timed Games.
od: Bouyer, P, et al.
Izdano: (2009)

Reachability Deficits in Quantum Approximate Optimization of Graph Problems
od: V. Akshay, et al.
Izdano: (2021-08-01)

Reachability under Contextual Locking
od: Remi Bonnet, et al.
Izdano: (2013-09-01)

A memory efficient reachability data structure through bit vector compression
od: van Schaik, S, et al.
Izdano: (2011)

A memory efficient reachability data structure through bit vector compression.
od: Schaik, S, et al.
Izdano: (2011)

Stubborn Set Reduction for Two-Player Reachability Games
od: Frederik Meyer Bønneland, et al.
Izdano: (2021-03-01)

Reachability Analysis for Annotated Code
od: Janota, M, et al.
Izdano: (2007)

Revisiting reachability in timed automata
od: Quaas, K, et al.
Izdano: (2017)

Reachability Switching Games
od: John Fearnley, et al.
Izdano: (2021-04-01)

Constraint-based reachability
od: Arnaud Gotlieb, et al.
Izdano: (2013-02-01)

Expected Reachability−Time Games
od: Forejt, V, et al.
Izdano: (2010)