Checking implementation

[Pedro Paiva]

Hi,

Currently, TLA+ does not support checking temporal formulas with existential quantifier (\EE) of temporal logic. For example, suppose I have two modules M1 and M2 and I would like to verify that M2 implements M1, but with some variables of M1, hidden. Let's say

M1 has variables x,y,z

M2 has variables x,y,z,w

y and z should be treated as internal. So

M1(y,z) == INSTANCE M1

M2!Spec => \EE y, z : M1(y,z)!Spec

Can I check it somehow? Thanks.

Best regards,

Pedro

--

Pedro Yuri Arbs Paiva

Engenheiro Eletrônico

Instituto Tecnológico de Aeronáutica (T-16)

(+55) 12 98106-4129

[Ron Pressler]

Hi.

The only way you can currently check it in TLC is with a refinement mapping (from M2 to M1) that you have to write yourself. In your case it seems simple enough as M2's state contains M1's, so it's a trivial matter (just Spec => M1!Spec [1]). In other cases, adding auxiliary variables is necessary, and may make this harder.

The theoretical issue is that the problem of checking temporal existential quantification is co-NP-hard in the number of states. I once started to think of an algorithm that may be able to do it in linear time for some/many practical instances but put it aside for now.

Ron

[1]: In general for existential quantification, A ⇒ B ⊦ A ⇒ ∃x. B

[Pedro Paiva]

Ok, so I should try with refinement maps. I did make it clear, but the variables y and z behave differently in M1 and M2, that's why I want to hide them. When TLC checks the property Spec => M1!Spec, it looks for variables with same names (in M1 and in M2) and compares their behaviors, is it correct? So my problem would be solved if I changed the names of y and z in module M1? Thanks

Pedro

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@googlegroups.com.
To post to this group, send email to tla...@googlegroups.com.
Visit this group at https://groups.google.com/group/tlaplus.
For more options, visit https://groups.google.com/d/optout.

[Ron Pressler]

Oh, even if they are different there is no need to change their names, but you will need to write a non-trivial refinement map (e.g. M1 ≜ INSTANCE M1 WITH y ← y*5, z ← z - w). If they are very different (the specs progress at different speeds etc.) you may need to add auxiliary variables to M2, which you'd use in the refinement mapping to calculate M2's y and z.