ML p(r)ior | Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete

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

2016-02-01
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-05-03

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

Highlights - Most important sentences from the article

2018-06-30

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-05-31
1706.00080 | math.AG

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

Highlights - Most important sentences from the article

2018-02-19

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

Highlights - Most important sentences from the article

2017-06-22

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

Highlights - Most important sentences from the article

2018-10-26
1810.11344 | cs.LG

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-02-06

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

Highlights - Most important sentences from the article

2018-07-21

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

Highlights - Most important sentences from the article

2019-03-19

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

Highlights - Most important sentences from the article

2017-06-16

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

Highlights - Most important sentences from the article

2015-10-19

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

Highlights - Most important sentences from the article

2017-07-21

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
PDF

Highlights - Most important sentences from the article

2018-11-08

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