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

書誌詳細
主要な著者:	Blondin, M, Englert, M, Finkel, A, Göller, S, Haase, C, Lazic, R, McKenzie, P, Totzke, P
フォーマット:	Journal article
言語:	English
出版事項:	Association for Computing Machinery 2021

類似資料

A polynomial-time algorithm for reachability in branching VASS in dimension one
著者:: Göller, S, 等
出版事項: (2016)

Logics for Continuous Reachability in Petri Nets and Vector Addition Systems with States
著者:: Haase, C, 等
出版事項: (2017)

The Complexity of Reachability in Affine Vector Addition Systems with States
著者:: Michael Blondin, 等
出版事項: (2021-07-01)

Directed reachability for infinite-state systems
著者:: Blondin, M, 等
出版事項: (2021)

Vector Addition System Reversible Reachability Problem
著者:: Jérôme Leroux
出版事項: (2013-02-01)

The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
著者:: leroux jerome
出版事項: (2010-09-01)

Vector reachability problem in SL (2, ℤ)
著者:: Potapov, I, 等
出版事項: (2016)

Affine extensions of integer vector addition systems with states
著者:: Blondin, M, 等
出版事項: (2018)

Strategy complexity of reachability in countable stochastic 2-player games
著者:: Kiefer, S, 等
出版事項: (2024)

Bounded Reachability Problems are Decidable in FIFO Machines
著者:: Benedikt Bollig, 等
出版事項: (2022-01-01)

Vector and scalar reachability problems in SL(2, Z)
著者:: Potapov, I, 等
出版事項: (2018)

On reachability problems for low-dimensional matrix semigroups
著者:: Colcombet, T, 等
出版事項: (2019)

Affine extensions of integer vector addition systems with states
著者:: Blondin, M, 等
出版事項: (2021)

Affine Extensions of Integer Vector Addition Systems with States
著者:: Michael Blondin, 等
出版事項: (2021-07-01)

On the Relationship between Reachability Problems in Timed and Counter Automata
著者:: Haase, C, 等
出版事項: (2012)

On the relationship between reachability problems in timed and counter automata
著者:: Haase, C, 等
出版事項: (2012)

Well Behaved Transition Systems
著者:: Michael Blondin, 等
出版事項: (2017-09-01)

On affine reachability problems
著者:: Jaax, S, 等
出版事項: (2020)

Link-Based Similarity Measures Using Reachability Vectors
著者:: Seok-Ho Yoon, 等
出版事項: (2014-01-01)

Reachability in Succinct and Parametric One−Counter Automata
著者:: Haase, C, 等
出版事項: (2009)

Reachability in Succinct and Parametric One-Counter Automata
著者:: Haase, C, 等
出版事項: (2009)

Construction of the Reachable Set for a Two-Dimensional Bilinear Impulsive Control System
著者:: D. Apanovich, 等
出版事項: (2016-03-01)

Reachability problems for linear dynamical systems
著者:: Chonev, V
出版事項: (2015)

The logical view on continuous petri net
著者:: Haase, CJ, 等
出版事項: (2017)

Deciding Reachability for 3-Dimensional Multi-Linear Systems
著者:: Olga Tveretina, 等
出版事項: (2011-06-01)

Reachability and escape problems in linear dynamical systems
著者:: Dcosta, J
出版事項: (2024)

Reachability problems in nondeterministic polynomial maps on the integers
著者:: Ko, SK, 等
出版事項: (2018)

Reachability Problem for Weak Multi-Pushdown Automata
著者:: Wojciech Czerwiński, 等
出版事項: (2013-09-01)

The pseudo-reachability problem for diagonalisable linear dynamical systems
著者:: D'Costa, J, 等
出版事項: (2022)

Estimates of Reachable Set and Sufficient Optimality Condition for Discrete Control Problems
著者:: S. P. Sorokin
出版事項: (2017-03-01)

Functional Reachability
著者:: Ong, C, 等
出版事項: (2009)

Reachability in Stochastic Timed Games.
著者:: Bouyer, P, 等
出版事項: (2009)

Reachability Deficits in Quantum Approximate Optimization of Graph Problems
著者:: V. Akshay, 等
出版事項: (2021-08-01)

Reachability under Contextual Locking
著者:: Remi Bonnet, 等
出版事項: (2013-09-01)

A memory efficient reachability data structure through bit vector compression
著者:: van Schaik, S, 等
出版事項: (2011)

A memory efficient reachability data structure through bit vector compression.
著者:: Schaik, S, 等
出版事項: (2011)

Reachability Analysis for Annotated Code
著者:: Janota, M, 等
出版事項: (2007)

Stubborn Set Reduction for Two-Player Reachability Games
著者:: Frederik Meyer Bønneland, 等
出版事項: (2021-03-01)

Revisiting reachability in timed automata
著者:: Quaas, K, 等
出版事項: (2017)

Reachability Switching Games
著者:: John Fearnley, 等
出版事項: (2021-04-01)