Re: [moca] Decidability of semantics

[Uwe Nestmann <Uwe.Nestmann@xxxxxxx>]

On 2 Mar, 2005, at 01:01, Lucian Wischik wrote:

> the second question, Engelfriet/Gelsema TR04-07 (May 2004): "to our 
> knowledge this question [of decidability of structural congruence] is 
> still open. In [Engelfriet TCS153/1996, Engelfriet/Gelsema 
> TCS211/1999] we have shown that adding four new structural laws, the 
> resulting 'extended congruence' is decidable".
>
> So I don't know for your second question either, but it was most 
> likely still open in May 2004, but perhaps pointlessly so because the 
> four extra structural laws are so reasonable...
>  !(P|Q) == !P | !Q
>  !!P == !P
>  !0 == 0
>  !P | !P == !P

Although, in another paper (in Acta Informatica 40, 385-430, 2004), 
they offer another variant by arguing slightly against the first of 
these four (IIRC), and call the result "middle congruence", which is 
apparently also decidable.

== Uwe ==

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