• 検索結果がありません。

Symbolic Bisimulations and Proof Systems for The $\pi$-Calculus(Concurrency Theory and Applications '96)

N/A
N/A
Protected

シェア "Symbolic Bisimulations and Proof Systems for The $\pi$-Calculus(Concurrency Theory and Applications '96)"

Copied!
2
0
0

(1)

Symbolic Bisimulations and Proof Systems for The

$\pi$

-Calculus

$*$

(Abstract)

Huimin

$\mathrm{L}\mathrm{i}\mathrm{n}^{\uparrow}$

Laboratory for Computer Science

Institute ofSoftware, Chinese Academy of Sciences

Axiomatisationsfor basic process algebras such as CCS, CSP, ACP, LOTOS..., are

based on equational logic. But purely equational reasoning is difficultfor the $\pi$-calculus

because here input prefixes introduce bound names, i.e. nameswhich are local within the

scope of the input prefixes and can be instantiated with arbitrary free names. Reflectedin

the axiomatisations this amounts to require when an input prefix is introduced the input

name must not be used before, a concept difficult to be formulated in the framework

of equational logic. The “symbolic” style proof system generalise equational logic by

using conditional equations of the form $\phi\triangleright T=U$ (where $\phi$ is a boolean condition on

names and $T,$ $U$ are process terms) as judgements. For each construct in the calculus

there corresponds an introduction rule in the core proof system. For instance the rule

for input prefix is

INPUT $\frac{\emptyset\triangleright\tau=U}{\phi\triangleright a(X).T=b(x).U}\phi\Rightarrow a=b$, $x\not\in n(\phi)$

Here $\phi$ represents the context condition for deriving $T=U$, and the side condition

ensures the input name $x$ is fresh.

In [Lin94] it is shown that, together with the standard CCS axioms for strong

bisim-ulation, this core proof system is sound and complete for late strong bisimulation in

recursion-free $\pi$-calculus. By adding either an inference rule dealing with early input

$([\mathrm{H}\mathrm{L}96])$ or an axiom schema $([\mathrm{P}\mathrm{S}93])$ proof systems for early bisimulation can be

ob-tained. In $[\mathrm{L}\mathrm{i}\mathrm{n}95\mathrm{a}]$ it is further shown that to extend these results to weak bisimulation

equivalences all what needed is the three $\tau$-laws $([\mathrm{M}\mathrm{i}189])$.

For the $\pi$-calculus with recursion the key inference rule is unique fixpoint induction.

It is syntactically identical to its pure-CCS counterpart $([\mathrm{M}\mathrm{i}184])$, but work at the level

of abstractions:

UFI $\frac{F=G[F/X]}{F=\mu XG}$ $X$ guarded in $G$

*Supportedbyresearch grants from the President Fund ofChineseAcademyofSciencesand National Natural Science Foundation ofChina.

$\uparrow \mathrm{T}\mathrm{h}\mathrm{e}$ author’s address: Institute

of Software, Chinese Academy of Sciences, $\mathrm{P}.\mathrm{O}$.Box 8718, Beijing

100080. Email: lhm@ox.ios.ac.cn.

(2)

where both $F$ and $G$ ar$e$

abstractions.

Extended

with this rule, and the

standard

rules for$\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}/\mathrm{u}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}$ recursions, the core proofsystem is sound and com-plete for strong

in

finite-control

$\pi$-calculus where

recursions

$\mathrm{a}r\mathrm{e}$

guarded

$([\mathrm{L}\mathrm{i}\mathrm{n}95\mathrm{b}])$. To achieve complet$e$ proof system for arbitrary recursions, the following

axiom can be adopted to reduce

unguarded

recursions to guarded ones:

UNG

fixX$( \vec{x})(\sum i\in I\emptyset i\nu\vec{X}_{i}’X(\vec{X}_{i})+T)=\mathrm{f}\mathrm{i}\mathrm{X}X(\vec{X})(\Sigma_{i\in I}\phi_{i}\nu\vec{x}_{i}’\tau[\vec{X}_{i}/\vec{x}]+^{\tau})$

where the

summands

in the recursion body satisfy certain saturationcondition.

Theproofs of the above

mentioned

completenessresults rely on thenotion of symbolic

bisimulation, first proposed in [HL95] for general

message-passing

process algebras. As

alternative characterisations ofthe

standard

definitionsofbisimulations inthe$\pi$-calculus,

symbolic bisimulations overcome the infinity inherited in the standard definitions by

employing finite partitions over the name space, instead of instantiating input names

and name parametersof recursivelydefined processes. Another powerful technical device

upon which the completeness proofs heavily rely is the notion of maximally consistent

name conditions.

Currently work is going on to extend the above results to weak bisimulation

equiva-lences in finite-cont$r\mathrm{o}1\pi$-calculus.

References

[HL95] M. Hennessy and H. Lin. Symbolic bisimulations.

Theoretical

Computer

Sci-ence, 138:353-389, 1995.

[HL96] M. Hennessy and H. Lin. Proof systems for

message-passing

process algebras.

Formal Aspects

of

Computing, 8:408-427,

1996.

[Lin94] H. Lin. Symbolic bisimulations and proof systems for the $\pi$-calculus. Report

7/94, Computer Science, University of Sussex, 1994.

[Lin95a] H. Lin. Complete inference systems for weak bisimulation equivalences in the

$\pi$-calculus. In Proceedings

Joint

Conference

on the

The-ory and Practice

of Software

Development, volume

915

of Lecture Notes in

Computer Science. Springer-Verlag,

1995.

[Lin95b] H. Lin. Unique fixpoint induction for the $\pi$-calculus. In Proceedings

Sixth

International

Conference

on Concurrency Theory, volume

962

of Lecture Notes in Computer

Science. Springer-Verlag, 1995.

[Mi184] R. Milner. A complete inference system for a class of regular behaviours. J.

Computer and System Science, 28:439-466,

1984.

[Mi189] R. Milner.

Communication

and Concurrency. Prentice-Hall,

1989.

[PS93] J. Parrow and D. Sangiorgi. Algebraictheories forname-passing calculi. Report

ECS-LFCS-93-262, LFCS, University of Edinburgh,

1993.

S49119 Style Classic Flexor Grade 7.0 Fixation Manual Weight 215g Size range 35 - 52 TECHNOLOGY-HIGHLIGHTS. •

Hence, the degree theory constructed in [1] is an extension of the classical Leray–Schauder degree in Hilbert space.. It is unique, single-valued and has the usual properties of

We prove a continuous embedding that allows us to obtain a boundary trace imbedding result for anisotropic Musielak-Orlicz spaces, which we then apply to obtain an existence result

(The Elliott-Halberstam conjecture does allow one to take B = 2 in (1.39), and therefore leads to small improve- ments in Huxley’s results, which for r ≥ 2 are weaker than the result

のようにすべきだと考えていますか。 やっと開通します。長野、太田地区方面

[Co] Coleman, R., On the Frobenius matrices of Fermat curves, \mathrm{p} ‐adic analysis, Springer. Lecture Notes in

[r]

Kiihleitner, An omega theorem on differences of two squares, $\mathrm{I}\mathrm{I}$ , Acta