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)

Affine extensions of integer vector addition systems with states
по: Blondin, M, и др.
Опубликовано: (2021)

On reachability problems for low-dimensional matrix semigroups
по: Colcombet, T, и др.
Опубликовано: (2019)

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)

The logical view on continuous petri net
по: Haase, CJ, и др.
Опубликовано: (2017)

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)

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)

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)

Stubborn Set Reduction for Two-Player Reachability Games
по: Frederik Meyer Bønneland, и др.
Опубликовано: (2021-03-01)

Reachability Analysis for Annotated Code
по: Janota, M, и др.
Опубликовано: (2007)

Revisiting reachability in timed automata
по: Quaas, K, и др.
Опубликовано: (2017)

Reachability Switching Games
по: John Fearnley, и др.
Опубликовано: (2021-04-01)

Constraint-based reachability
по: Arnaud Gotlieb, и др.
Опубликовано: (2013-02-01)

Relating Data Independent Trace Checks in CSP with UNITY Reachability under a Normality Assumption
по: Roscoe, A, и др.
Опубликовано: (2004)