A criterion for separating process calculi

Details A criterion for separating process calculi A criterion for separating process calculi

2010-11-30

arxiv.org/abs/1011.6430v1

EPTCS 41, 2010, pp. 16-30

Computer Science

Logic in Computer Science

In Proceedings EXPRESS'10, arXiv:1011.6012

Scientific paper

10.4204/EPTCS.41.2

We introduce a new criterion, replacement freeness, to discern the relative expressiveness of process calculi. Intuitively, a calculus is strongly replacement free if replacing, within an enclosing context, a process that cannot perform any visible action by an arbitrary process never inhibits the capability of the resulting process to perform a visible action. We prove that there exists no compositional and interaction sensitive encoding of a not strongly replacement free calculus into any strongly replacement free one. We then define a weaker version of replacement freeness, by only considering replacement of closed processes, and prove that, if we additionally require the encoding to preserve name independence, it is not even possible to encode a non replacement free calculus into a weakly replacement free one. As a consequence of our encodability results, we get that many calculi equipped with priority are not replacement free and hence are not encodable into mainstream calculi like CCS and pi-calculus, that instead are strongly replacement free. We also prove that variants of pi-calculus with match among names, pattern matching or polyadic synchronization are only weakly replacement free, hence they are separated both from process calculi with priority and from mainstream calculi.

Affiliated with

Also associated with

No associations

Rating

A criterion for separating process calculi does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A criterion for separating process calculi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A criterion for separating process calculi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444491