We develop a polynomial translation from finite control pi-calculus processes to safe low-level Petri nets. To our knowledge, this is the first such translation. It is natural in that there is a close correspondence between the control flows, enjoys a bisimulation result, and is suitable for practical model checking.
Although several translations of to Petri nets have been proposed, none of them provides a polynomial translation of FCPs to safe PNs. The verification kit HAL @cite_8 translates a model into a --- a finite automaton where states are labelled by sets of names that represent restrictions @cite_14 @cite_23 . For model checking, these automata are further translated to finite automata @cite_8 . Like in our approach, the idea is to replace restrictions with fresh names, but the translation stores full substitutions, which may yield an exponential blow up of the finite automaton. Our translation avoids this blow up by compactly representing substitutions by PN markings. This, however, needs careful substitution manipulation and reference counting.
@cite_14 @cite_23 @cite_8
1839078145 2070368511
In this paper we associate to every π-calculus agent an irredundant unfolding, i.e., a labeled transition system equipped with the ordinary notion of strong bisimilarity, so that agents are mapped into strongly bisimilar unfoldings if and only if they are early strongly bisimilar. For a class of finitary agents (that strictly contains the finite control agents) without matching, the corresponding unfoldings are finite and can be built efficiently. The main consequence of the results presented in the paper is that the irredundant unfolding can be constructed also for a single agent, and then a minimal realization can be derived from it employing the ordinary partition refinement algorithm. Instead, according toprevious results only pairs of π-calculus agents could be unfolded and tested for bisimilarity, and no minimization of a single agent was possible. Another consequence is the improvement of the complexity bound for checking bisimilarity of finitary agents without matching. This article presents a semantic-based environment for reasoning about the behavior of mobile systems. The verification environment, called HAL, exploits a novel automata-like model that allows finite-state verification of systems specified in the π-calculus. The HAL system is able to interface with several efficient toolkits (e.g. model-checkers) to determine whether or not certain properties hold for a given specification. We report experimental results on some case studies.