CITI has stopped operations in 2014, to co-launch NOVA LINCS THIS SITE IS NOT BEING UPDATED SINCE 2013
citi banner
Home Page FCT/UNL UNL
  Home  \  Publications  \  Article Page Login  
   
banner bottom
File Top
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 bisimilar- ity, 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.


Journal: Information and Computation (Elsevier) ( United States )

Volume: 209

Number: 2

Pages: 198 to 226


Date: February, 2011


Authors:
    Ivan Lanese (Universitá di Bologna), Jorge A. Pérez, Davide Sangiorgi (Universitá di Bologna), Alan Schmitt (INRIA)
File Bottom