Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
On detecting deadlock in the Pi-Calculus

Edit abstract data

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

Abstract

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 Valid HTML 4.01! Valid CSS!