Search

• < Previous
• 1
• Next >

---

Shortest paths in one-counter systems

Dmitry Chistikov ; Wojciech Czerwiński ; Piotr Hofman ; Michał Pilipczuk ; Michael Wehar.

We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some word of length at most $O(n^2)$. This closes the gap between the previously known upper bound of $O(n^3)$ and lower bound of $\Omega(n^2)$. More generally, we prove a tight upper bound on the length of&nbsp;[&hellip;]

---

Linear equations for unordered data vectors in $[D]^k\to{}Z^d$

Piotr Hofman ; Jakub Różycki.

Following a recently considered generalisation of linear equations to unordered-data vectors and to ordered-data vectors, we perform a further generalisation to data vectors that are functions from k-element subsets of the unordered-data set to vectors of integer numbers. These generalised equations&nbsp;[&hellip;]

---