On the relative succinctness of some modal logics



Iliev, Petar
On the relative succinctness of some modal logics. [Unspecified]

[img] PDF
Petar_Iliev_PhD_Thesis.pdf - Accepted Version
Access to this file is embargoed until Unspecified.
Available under License Creative Commons Attribution No Derivatives.

Download (1MB)
[img] PDF (IlievPet_Nov2013_14481.pdf)
IlievPet_Nov2013_14481.pdf
Available under License Creative Commons Attribution No Derivatives.

Download (1MB)

Abstract

The aim of this thesis is to compare several extensions of multimodal logic in terms of their representational succinctness on different classes of models. Succinctness is a natural refinement on the notion of expressivity. Intuitively, given two logics L1 and L2, we say that L1 expresses more succinctly than L2 some properties of a class of models if the L1-formulae expressing the properties in question are significantly shorter than all the equivalent L2-formulae. The precise technical interpretation of "significantly shorter" depends on the case at hand and may mean "exponentially shorter", "nonelementary shorter", etc. This work was motivated by the question of whether public announcement logic (PAL) is exponentially more succinct than multimodal logic (ML) on the class S5 of Kripke models with underlying structures in which all relations are reflexive, symmetric, and transitive. Using techniques based on a generalisation of Ehrenfeucht-Fra��ss�e games called Adler- Immerman games, we show that extending ML in two di�erent ways: by allowing formulae [[

Item Type: Unspecified
Additional Information: Date: 2013-11 (completed)
Divisions: ?? dep_compsci ??
Depositing User: Symplectic Admin
Date Deposited: 19 Feb 2014 09:50
Last Modified: 09 Jan 2021 08:54
URI: https://livrepository.liverpool.ac.uk/id/eprint/14481