### Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete

**2016-02-01**

1602.00477 | cs.LO

Blondin et al. showed at LICS 2015 that two-dimensional vector addition
systems with states have reachability witnesses of length exponential in the
number of states and polynomial in the norm of vectors. The resulting
guess-and-verify algorithm is optimal (PSPACE), but only if the input vectors
are given in binary. We answer positively the main question left open by their
work, namely establish that reachability witnesses of pseudo-polynomial length
always exist. Hence, when the input vectors are given in unary, the improved
guess-and-verify algorithm requires only logarithmic space.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-05-03**

1905.01185 | cs.CG

We study continuous analogues of "vitality" for discrete network flows/paths,
and consider problems … show more

**2018-06-30**

1807.00109 | math.CO

The parity of the length of paths and cycles is a classical and well-studied
topic in graph theory a… show more

**2019-03-17**

1903.07172 | math.MG

Given a set of sources and a set of sinks as points in the Euclidean plane, a
directed network is a … show more

**2018-07-25**

1807.09498 | cs.CG

We consider a range-search variant of the closest-pair problem. Let
$\varGamma$ be a fixed shape in … show more

**2017-05-31**

1706.00080 | math.AG

Tropical algebra emerges in many fields of mathematics such as algebraic
geometry, mathematical phys… show more

**2018-02-19**

1802.06575 | math.OC

We consider the decidability of state-to-state reachability in linear
time-invariant control systems… show more

**2017-06-22**

1706.07473 | cs.CG

We describe and analyze an algorithm for computing the homology (Betti
numbers and torsion coefficie… show more

**2018-10-26**

1810.11344 | cs.LG

Expectation Maximization (EM) is among the most popular algorithms for
maximum likelihood estimation… show more

**2017-09-11**

1709.03294 | cs.SC

We give a separation bound for the complex roots of a trinomial $f \in
\mathbb{Z}[X]$. The logarithm… show more

**2019-02-06**

1902.01998 | math.ST

We propose an estimator for the mean of a random vector in $\mathbb{R}^d$
that can be computed in ti… show more

**2018-07-21**

1807.08139 | cs.SY

We consider a class of continuous-time hybrid dynamical systems that
correspond to subgradient flows… show more

**2019-03-19**

1903.07913 | cs.FL

Reaction systems are discrete dynamical systems inspired by bio-chemical
processes, whose dynamical … show more

**2017-06-16**

1706.05975 | math.CO

We discuss five discrete results: the lemmas of Sperner and Tucker from
combinatorial topology and t… show more

**2015-10-19**

1510.05460 | cs.FL

We show that any one-counter automaton with $n$ states, if its language is
non-empty, accepts some w… show more

**2017-07-21**

1707.06856 | math.CO

We say that a finite set of red and blue points in the plane in general
position can be $K_{1,3}$-co… show more

**2018-11-08**

1811.03591 | cs.DS

We introduce and study the notion of an outer bi-Lipschitz extension of a map
between Euclidean spac… show more