Iliev, Petar
On the relative succinctness of some modal logics.
Doctor of Philosophy thesis, University of Liverpool.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
Petar_Iliev_PhD_Thesis.pdf - Author Accepted Manuscript Access to this file is embargoed until Unspecified. Available under License Creative Commons Attribution No Derivatives. Download (1MB) |
|
PDF (IlievPet_Nov2013_14481.pdf)
IlievPet_Nov2013_14481.pdf - Unspecified 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: | Thesis (Doctor of Philosophy) |
|---|---|
| Additional Information: | Date: 2013-11 (completed) |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 19 Feb 2014 09:50 |
| Last Modified: | 16 Dec 2022 04:41 |
| DOI: | 10.17638/00014481 |
| Supervisors: |
|
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/14481 |
Dimensions
Dimensions
