Skip to Main content Skip to Navigation
Journal articles

On the Expressiveness and Decidability of Higher-Order Process Calculi

Abstract : In higher-order process calculi, the values exchanged in communications may contain processes. A core calculus of higher-order concurrency is studied; it has only the operators necessary to express higher-order communications: input prefix, process output, and parallel composition. By exhibiting a deterministic encoding of Minsky machines, the calculus is shown to be Turing complete. Therefore its termination problem is undecidable. Strong bisimilarity, however, is shown to be decidable. Furthermore, the main forms of strong bisimilarity for higher-order processes (higher-order bisimilarity, context bisimilarity, normal bisimilarity, barbed congruence) coincide. They also coincide with their asynchronous versions. A sound and complete axiomatization of bisimilarity is given. Finally, bisimilarity is shown to become undecidable if at least four static (i.e., top-level) restrictions are added to the calculus.
Complete list of metadatas

Cited literature [50 references]  Display  Hide  Download

https://hal.inria.fr/hal-01112294
Contributor : Alan Schmitt <>
Submitted on : Monday, February 2, 2015 - 3:45:50 PM
Last modification on : Friday, July 10, 2020 - 4:21:45 PM
Document(s) archivé(s) le : Wednesday, May 27, 2015 - 3:43:14 PM

File

Lanese2011On-the-Expressivenes...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Ivan Lanese, Jorge Perez, Davide Sangiorgi, Alan Schmitt. On the Expressiveness and Decidability of Higher-Order Process Calculi. Journal of Information and Computation, Elsevier, 2011, 209 (2), pp.29. ⟨10.1016/j.ic.2010.10.001⟩. ⟨hal-01112294⟩

Share

Metrics

Record views

2087

Files downloads

249