On the expressiveness and decidability of higher-order process calculi

Ivan Lanese, Jorge A. Perez, Davide Sangiorgi*, Alan Schmitt

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)
48 Downloads (Pure)

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. (C) 2010 Elsevier Inc. All rights reserved.

Original languageEnglish
Pages (from-to)198-226
Number of pages29
JournalInformation and Computation
Volume209
Issue number2
DOIs
Publication statusPublished - Feb-2011
Externally publishedYes

Keywords

  • Process calculi
  • Higher-order communication
  • Bisimulation
  • Expressiveness
  • PI-CALCULUS
  • HOWES METHOD
  • BISIMULATIONS
  • PASSIVATION
  • REPLICATION
  • EQUIVALENCE
  • LANGUAGES
  • POWER

Cite this