[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Checking implementation


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.


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