On decidability properties of two fragments of the asynchronous π-calculus
Main Article Content
In (Cacciagrano, et al., 2008) the authors studied the expressiveness of persistence in the asynchronous π-calculus, henceforth Aπ. They consideredAπ and three sub-languages of it, each capturing one source of persistence: the persistent-input calculus (PIAπ), the persistent-output calculus (POAπ), and the persistent calculus (PAπ). They prove that, under some general conditions, there cannot be an encoding from Aπinto a (semi)-persistent calculus preserving the must-testing semantics, a semantics sensitive to divergence. In this paper we support and strengthen the separation results of (Cacciagrano, et al., 2008) by showing that convergence and divergence are two decidable properties in a fragment of POAπ and PAπ, in contrast to what happen in Aπ. Thus, it is shown that there cannot be a (computable) encoding from Aπ into PAπ and in such a fragment of POAπ, preserving divergence or convergence. These impossibility results don’t presuppose any condition on the encodings and involve directly convergence for first time in the study of the expressiveness of persistence of Aπ.
Authors grant the journal and Universidad del Valle the economic rights over accepted manuscripts, but may make any reuse they deem appropriate for professional, educational, academic or scientific reasons, in accordance with the terms of the license granted by the journal to all its articles.
Articles will be published under the Creative Commons 4.0 BY-NC-SA licence (Attribution-NonCommercial-ShareAlike).