engleski

A good method of transforming Veltman into Verbrugge models

Generalised Veltman semantics for interpretability logic, or nowadays called Verbrugge semantics (in honor of Rineke Verbrugge), was developed to obtain certain non-derivability results since Veltman semantics for interpretability logic is not fine-grained enough for certain applications. It has turned out that this semantics has various good properties. A. Dawar and M. Otto developed a models-for-games method, which provides conditions from which a Van Benthem characterisation theorem over a particular class of models immediately follows. M. Vuković and T. Perkov proved that this result can be extended to Veltman models for the interpretability logic IL. They used bisimulation games on Veltman models for interpretability logic to prove that. To prove similar result for Verbrugge semantics, one needs to define bisimulations and bisimulation games for Verbrugge semantics (and also their finite counterparts, n-bisimulations and n-bisimulation games). It turns out that the notion of bisimulation for Verbrugge semantics as defined in past papers is not good enough. It can easily be shown that two n-bisimilar worlds are n-modally equivalent, but a standard result that the converse is true (if we take a finite set of propositional variables), does not hold. So, we have defined a new notion of weak bisimulations (or short, wbisimulations), their corresponding games called weak bisimulation games and their finite approximations: n-w-bisimulations and weak n-bisimulation games. We will present these new notions and then we will show that for Verbrugge semantics, w-bisimulation is strictly stronger than the modal equivalence. That is, there are two modally equivalent worlds in two Verbrugge models that are not w-bisimilar. In order to do that, first we will present two Veltman models which were used by Cačić and Vrgoč and which are counterexamples for Veltman semantics. Then we will present a method for liftin two Veltman models to Verbrugge models, and apply it to the presented counterexamples for Veltman semantics. Finally, we will show the main result: our method preserves (in a way) bisimulations. More precisely, two worlds are bisimilar as worlds in Veltman models if and only if they are w-bisimilar as worlds in Verbrugge models that were obtained by applying our method to the Veltman ones.

interpretability logic ; Verbrugge semantics ; w-bisimulations ; weak bisimulation games ; modal equivalence

nije evidentirano