Logics in Computer Science by Fabio Mogavero

Author:Fabio Mogavero
Language: eng
Format: epub
Publisher: Atlantis Press, Paris

The following theorem summarizes the principal negative properties of MCtl under the and semantics.

Theorem 2.1

(Negative Properties) For MPml, MCtl, MCtl , and MCtl under both the and semantics, it holds that:(1)they do not have the tree model property;

(2)they are not invariant under unwinding;

(3)they are not invariant under bisimulation.

Proof

[Item 1] To prove the statement, we consider a formula with an existential minimal model quantifier such that it requires to extract a graph submodel that, in order to be satisfied, cannot be a tree. Consider the MPml formula , where , , , , , and . This formula is satisfiable. In Fig. 2.2, we show the Kss , , , and as the only minimal models of , where only is a tree and and are the only models of . Indeed, and satisfy , but and do not. Since any model of has to include or as submodel, it follows that no tree model can satisfy . Since MPml is a sublogic of MCtl, MCtl , and MCtl , the thesis easily follows.

[Item 2] By the previous item, there exists a satisfiable MPml formula that does not have a tree model. Now, let be its model and the related unwinding. Then, we have that and . Hence, MPml cannot be invariant under unwinding.

[Item 3] Since an unwinding is a particular case of a bisimilarity relation, we have also that MPml is not invariant under bisimulation, i.e., it is possible to express an MPml property satisfied on a model , but not on one of its bisimilar models .

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.