Re: [moca] Decidability of semantics

["Lucian Wischik" <lu@xxxxxxxxxxx>]

> Has it been determined exactly under what circumstances it is decidable 
> what transitions an agent has? [snip]
> A related question is decidability of structural congruence - is this 
> problem still open?

I don't know for your first question.

For 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

--
Lucian

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