Search

• < Previous
• 1
• Next >

---

Reachability Analysis of Communicating Pushdown Systems

Alexander Heussner ; Jérôme Leroux ; Anca Muscholl ; Grégoire Sutre.

The reachability analysis of recursive programs that communicate asynchronously over reliable FIFO channels calls for restrictions to ensure decidability. Our first result characterizes communication topologies with a decidable reachability problem restricted to eager runs (i.e., runs where messages&nbsp;[&hellip;]

---

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;]

---