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

Detaylı Bibliyografya
Asıl Yazarlar:	Blondin, M, Englert, M, Finkel, A, Göller, S, Haase, C, Lazic, R, McKenzie, P, Totzke, P
Materyal Türü:	Journal article
Dil:	English
Baskı/Yayın Bilgisi:	Association for Computing Machinery 2021

Benzer Materyaller

A polynomial-time algorithm for reachability in branching VASS in dimension one
Yazar:: Göller, S, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

Logics for Continuous Reachability in Petri Nets and Vector Addition Systems with States
Yazar:: Haase, C, ve diğerleri
Baskı/Yayın Bilgisi: (2017)

The Complexity of Reachability in Affine Vector Addition Systems with States
Yazar:: Michael Blondin, ve diğerleri
Baskı/Yayın Bilgisi: (2021-07-01)

Directed reachability for infinite-state systems
Yazar:: Blondin, M, ve diğerleri
Baskı/Yayın Bilgisi: (2021)

Vector Addition System Reversible Reachability Problem
Yazar:: Jérôme Leroux
Baskı/Yayın Bilgisi: (2013-02-01)

The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
Yazar:: leroux jerome
Baskı/Yayın Bilgisi: (2010-09-01)

Vector reachability problem in SL (2, ℤ)
Yazar:: Potapov, I, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

Affine extensions of integer vector addition systems with states
Yazar:: Blondin, M, ve diğerleri
Baskı/Yayın Bilgisi: (2018)

Strategy complexity of reachability in countable stochastic 2-player games
Yazar:: Kiefer, S, ve diğerleri
Baskı/Yayın Bilgisi: (2024)

Bounded Reachability Problems are Decidable in FIFO Machines
Yazar:: Benedikt Bollig, ve diğerleri
Baskı/Yayın Bilgisi: (2022-01-01)

Vector and scalar reachability problems in SL(2, Z)
Yazar:: Potapov, I, ve diğerleri
Baskı/Yayın Bilgisi: (2018)

Affine extensions of integer vector addition systems with states
Yazar:: Blondin, M, ve diğerleri
Baskı/Yayın Bilgisi: (2021)

On reachability problems for low-dimensional matrix semigroups
Yazar:: Colcombet, T, ve diğerleri
Baskı/Yayın Bilgisi: (2019)

Affine Extensions of Integer Vector Addition Systems with States
Yazar:: Michael Blondin, ve diğerleri
Baskı/Yayın Bilgisi: (2021-07-01)

On the Relationship between Reachability Problems in Timed and Counter Automata
Yazar:: Haase, C, ve diğerleri
Baskı/Yayın Bilgisi: (2012)

On the relationship between reachability problems in timed and counter automata
Yazar:: Haase, C, ve diğerleri
Baskı/Yayın Bilgisi: (2012)

Well Behaved Transition Systems
Yazar:: Michael Blondin, ve diğerleri
Baskı/Yayın Bilgisi: (2017-09-01)

On affine reachability problems
Yazar:: Jaax, S, ve diğerleri
Baskı/Yayın Bilgisi: (2020)

Link-Based Similarity Measures Using Reachability Vectors
Yazar:: Seok-Ho Yoon, ve diğerleri
Baskı/Yayın Bilgisi: (2014-01-01)

The logical view on continuous petri net
Yazar:: Haase, CJ, ve diğerleri
Baskı/Yayın Bilgisi: (2017)

Reachability in Succinct and Parametric One−Counter Automata
Yazar:: Haase, C, ve diğerleri
Baskı/Yayın Bilgisi: (2009)

Reachability in Succinct and Parametric One-Counter Automata
Yazar:: Haase, C, ve diğerleri
Baskı/Yayın Bilgisi: (2009)

Construction of the Reachable Set for a Two-Dimensional Bilinear Impulsive Control System
Yazar:: D. Apanovich, ve diğerleri
Baskı/Yayın Bilgisi: (2016-03-01)

Reachability problems for linear dynamical systems
Yazar:: Chonev, V
Baskı/Yayın Bilgisi: (2015)

Reachability and escape problems in linear dynamical systems
Yazar:: Dcosta, J
Baskı/Yayın Bilgisi: (2024)

Reachability problems in nondeterministic polynomial maps on the integers
Yazar:: Ko, SK, ve diğerleri
Baskı/Yayın Bilgisi: (2018)

Reachability Problem for Weak Multi-Pushdown Automata
Yazar:: Wojciech Czerwiński, ve diğerleri
Baskı/Yayın Bilgisi: (2013-09-01)

The pseudo-reachability problem for diagonalisable linear dynamical systems
Yazar:: D'Costa, J, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

Functional Reachability
Yazar:: Ong, C, ve diğerleri
Baskı/Yayın Bilgisi: (2009)

Reachability in Stochastic Timed Games.
Yazar:: Bouyer, P, ve diğerleri
Baskı/Yayın Bilgisi: (2009)

Reachability Deficits in Quantum Approximate Optimization of Graph Problems
Yazar:: V. Akshay, ve diğerleri
Baskı/Yayın Bilgisi: (2021-08-01)

Reachability under Contextual Locking
Yazar:: Remi Bonnet, ve diğerleri
Baskı/Yayın Bilgisi: (2013-09-01)

A memory efficient reachability data structure through bit vector compression
Yazar:: van Schaik, S, ve diğerleri
Baskı/Yayın Bilgisi: (2011)

A memory efficient reachability data structure through bit vector compression.
Yazar:: Schaik, S, ve diğerleri
Baskı/Yayın Bilgisi: (2011)

Stubborn Set Reduction for Two-Player Reachability Games
Yazar:: Frederik Meyer Bønneland, ve diğerleri
Baskı/Yayın Bilgisi: (2021-03-01)

Reachability Analysis for Annotated Code
Yazar:: Janota, M, ve diğerleri
Baskı/Yayın Bilgisi: (2007)

Revisiting reachability in timed automata
Yazar:: Quaas, K, ve diğerleri
Baskı/Yayın Bilgisi: (2017)

Reachability Switching Games
Yazar:: John Fearnley, ve diğerleri
Baskı/Yayın Bilgisi: (2021-04-01)

Constraint-based reachability
Yazar:: Arnaud Gotlieb, ve diğerleri
Baskı/Yayın Bilgisi: (2013-02-01)

Relating Data Independent Trace Checks in CSP with UNITY Reachability under a Normality Assumption
Yazar:: Roscoe, A, ve diğerleri
Baskı/Yayın Bilgisi: (2004)