Can I read Reachability Analysis of Communicating Pushdown Systems on EtoBox?

Reachability Analysis of Communicating Pushdown Systems by Heussner, Alexander; Leroux, Jérôme; Muscholl, Anca; Sutre, Grégoire is a scholarly article available to read on EtoBox.

What is Reachability Analysis of Communicating Pushdown Systems about?

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 are either received immediately after being sent, or never received). The problem is EXPTIME-complete in the decidable case. The second result is a doubly exponential time algorithm for bounded context analysis in this setting, together with a matching lower bound. Both results extend and improve previous work from La Torre et al.

Author

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

Published

2012

Language

EN