Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
On detecting deadlock in the Pi-Calculus

Author(s): Tiago Azevedo, Mario Benevides, Fabio Protti and Marcelo Sihman
Slot: Array, 12:00-12:20, col. 5


In this work we deal with the notions of deadlock in the asynchronous
polyadic Pi-calculus. Based on the proposed definitions, we show that detecting
deadlock in the asynchronous polyadic pi-calculus is usually an undecidable
problem. However, when restricting the language by forbidding replicating input
prefixed processes, the detection turns out to be decidable, and a polynomial
deadlock detection algorithm is presented.

websites: Arnold Beckmann 2008-05-19