Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twenty-Third Annual IEEE Symposium on

Logic in Computer Science (LICS 2008)

Paper: On the Expressiveness and Decidability of Higher-Order Process Calculi (at LICS 2008)

Authors: Ivan Lanese Jorge A. Perez Davide Sangiorgi Alan Schmitt

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 nearly deterministic encoding of Minsky machines, the calculus is shown to be Turing complete and therefore its termination problem is undecidable. Strong bisimilarity, however, is shown to be decidable. Further, 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.

BibTeX

  @InProceedings{LanesePerezSangiorg-OntheExpressiveness,
    author = 	 {Ivan Lanese and Jorge A. Perez and Davide Sangiorgi and Alan Schmitt},
    title = 	 {On the Expressiveness and Decidability of Higher-Order Process Calculi},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {145--155},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski