SODA

Model Checking Mobile Processes (Full version)

Dam, Mads (1994) Model Checking Mobile Processes (Full version). [SICS Report]

[img]Postscript
146Kb

Abstract

We introduce a temporal logic for the polyadic pi-calculus based on fixed point extensions of Hennessy-Milner logic. Features are added to account for parametrisation, generation, and passing of names, including the use, following Milner, of dependent sum and product to account for (unlocalised) input and output, and explicit parametrisation on names using lambda-abstraction and application. The latter provides a single name binding mechanism supporting all parametrisation needed. A proof system and decision procedure is developed based on Stirling and Walker's approach to model checking the modal mu-calculus using constants. One difficulty, for both conceptual and efficiency-based reasons, is to avoid the explicit use of the omega-rule for parametrised processes. A key idea, following Hennessy and Lin's approach to deciding bisimulation for certain types of value-passing processes, is the relativisation of correctness assertions to conditions on names. Based on this idea a proof system and decision procedure is obtained for arbitrary pi-calculus processes with finite control, pi-calculus correlates of CCS finite-state processes, avoiding the use of parallel composition in recursively defined processes.

Item Type:SICS Report
Uncontrolled Keywords:Temporal Logic, Process Algebra, Mobile Processes, Model Checking
ID Code:2123
Deposited By:Vicki Carleson
Deposited On:22 Oct 2007
Last Modified:18 Nov 2009 16:00

Repository Staff Only: item control page