Search

• < Previous
• 1
• Next >

---

Minimization of visibly pushdown automata is NP-complete

Olivier Gauwin ; Anca Muscholl ; Michael Raskin.

We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such that each language is associated with an initial&nbsp;[&hellip;]

---

Affine Extensions of Integer Vector Addition Systems with States

Michael Blondin ; Christoph Haase ; Filip Mazowiecki ; Mikhail Raskin.

We study the reachability problem for affine $\mathbb{Z}$-VASS, which are integer vector addition systems with states in which transitions perform affine transformations on the counters. This problem is easily seen to be undecidable in general, and we therefore restrict ourselves to affine&nbsp;[&hellip;]

---

The Complexity of Reachability in Affine Vector Addition Systems with States

Michael Blondin ; Mikhail Raskin.

Vector addition systems with states (VASS) are widely used for the formal verification of concurrent systems. Given their tremendous computational complexity, practical approaches have relied on techniques such as reachability relaxations, e.g., allowing for negative intermediate counter values. It&nbsp;[&hellip;]

---