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

---

Pumping lemmas for weighted automata

Agnishom Chattopadhyay ; Filip Mazowiecki ; Anca Muscholl ; Cristian Riveros.

We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by unambiguous, finitely-ambiguous,&nbsp;[&hellip;]

---