Swap Logic

Abstract. We investigate dynamic modal operators that can change the model during evaluation. We define the logic SL by extending the basic modal language with the ♦ modality, which is a diamond operator that in addition has the ability to invert pairs of related elements in the domain while traversing an edge of the accessibility relation. SL is very expressive: it fails to have the finite and the tree model prop-erty. We show that SL is equivalent to a fragment of first-order logic by providing a satisfiability preserving translation. In addition, we provide an equivalence preserving translation from SL to the hybrid logicH(:, ↓). We also define a suitable notion of bisimulation for SL and investigate its expressive power, showing that it lies strictly between the basic modal logic and H(:, ↓). We finally show that its model checking problem is PSpace-complete and its satisfiability problem is undecidable