Skip Navigation

The Computer Journal 1994 37(4):233-242; doi:10.1093/comjnl/37.4.233
© 1994 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (7)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Christensen, S.
Right arrow Articles by Moller, F.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Decidable Subsets of CCS

S. Christensen *, Y. Hirshfeld § and F. Moller ¶

Laboratory for Foundations of Computer Science, University of Edinburgh, Edinburgh EH9 3JZ, UK

CCS is a universal formalism: any computable function is computed by some CCS agent. Moreover, one can reduce the halting problem for Turing machines to the problem of deciding bisimilarity of two CCS agents, thus demonstrating the undecidability of the equivalence checking problem. In this paper, we demonstrate the limits of decidability of CCS. In particular, we show that by simply disallowing either of communication or both restriction and relabelling, we arrive at a sub-language which still describes a rich class of infinite state systems but for which bisimulation is decidable. We also demonstrate complete axiomatisations for these sublanguages. We compare these results with the undecidability of all other common equivalences.


* Currently at Systematic Software Engineering A/S, Aarhus.

§ On Sabbatical leave from The School of Mathematics and Computer Science, Tel Aviv University.

Currently at The Swedish Institute of Computer Science, Stockholm.

{ddagger} Laboratory for Foundations of Computer Science, University of Edinburgh, Edinburgh EH9 3JZ, UK


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.