A complete symbolic bisimulation for full applied pi calculus

摘要

Symbolic characterisations of bisimilarities for the applied pi calculus proposed so far are sound but incomplete, even restricted to the finite fragment of the calculus. In this paper we present a novel approach to symbolic semantics for the applied pi calculus, leading to a notion of symbolic bisimulation which is both sound and complete with respect to the standard labelled bisimilarity. Moreover, our framework accommodates replications hence works for the full calculus.