Re: question about structural congruence

[Uwe.Nestmann@xxxxxxx]

>>>>> "DH" == Daniel Hirschkoff <hirschko@xxxxxxxxxxx> writes:

DH> A key point in deciding structural congruence (which is
DH> needed to establish a notion of normal form for \equiv),
DH> though, is the addition of a law stating distributivity
DH> of replication w.r.t. parallel composition (and other
DH> less important properties of replication):

That said, I have not yet seen a proof that structural
congruence without these additional laws is _undecidable_.

>>>>> "JP" == Joachim Parrow <joachim@xxxxxxxxx> writes:

JP> A more ambitious attack would be to find a good model
JP> for structural congruence. I believe that is still open
JP> despite the ten years (someone here wanted open
JP> problems...)

At least the work by Engelfriet/Gelsema (TCS 211, 1999)
shows that structural congruence coincides with multiset
congruence in the context of their "small" pi-calculus.
(Similar to Milner's relation between static laws of CCS and
the algebra of flow graphs, IIRC.)

== Uwe ==
  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The "models for mobility" mailing list     mailto:moca@xxxxxxxxxxxxxxx
 http://www-sop.inria.fr/mimosa/personnel/Davide.Sangiorgi/moca.html