Copyright Information
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other
copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying
this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without
the explicit permission of the copyright holder.
show main publications
On the Expressiveness and Decidability of Higher-Order Process Calculi @INPROCEEDINGS{LPSS08, title = {{On the Expressiveness and Decidability of Higher-Order Process Calculi}}, author = {{Ivan} {Lanese} and {Jorge} {Perez Parra} and {Davide} {Sangiorgi} and {Alan} {Schmitt}}, booktitle = {Proc. of LICS'08}, pages = {145-155}, 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.
}, publisher = {IEEE Computer Society}, year = {2008}, url = {http://www.cs.unibo.it/~lanese/publications/fulltext/lics2008.ps.gz}, doi = {10.1109/LICS.2008.8}, invited = {N}, keywords = {bisimulation, process calculi}, partner = {UNIBO}, status = {public}, task = {T3.4}, }
|