Algorithmic properties of modal logics with restricted languages

Simple item page
dc.contributor.authorRybakov, Mikhail
dc.date.accessioned2019-08-29T13:02:50Z
dc.date.available2019-08-29T13:02:50Z
dc.date.issued2019
dc.descriptionA Thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfillment of the requirements for the degree of Doctor of Philosophy May 2019en_ZA
dc.description.abstractModal logics, both propositional and predicate, have been used in computer science since the late 1970s. One of the most important properties of modal logics of relevance to their applications in computer science is the complexity of their satisfiability problem. The complexity of satisfiability for modal logics is rather high: it ranges from NP-complete to undecidable for propositional logics and is undecidable for predicate logics. This has, for a long time, motivated research in drawing the borderline between tractable and intractable fragments of propositional modal logics as well as between decidable and undecidable fragments of predicate modal logics. In the present thesis, we investigate some very natural restrictions on the languages of propositional and predicate modal logics and show that placing those restrictions does not decrease complexity of satisfiability. For propositional languages, we consider restricting the number of propositional variables allowed in the construction of formulas, while for predicate languages, we consider restricting the number of individual variables as well as the number and arity of predicate letters allowed in the construction of formulas. We develop original techniques, which build on and develop the techniques known from the literature, for proving that satisfiability for a finite-variable fragment of a propositional modal logic is as computationally hard as satisfiability for the logic in the full language and adapt those techniques to predicate modal logics and prove undecidability of fragments of such logics in the language with a finite number of unary predicate letters as well as restrictions on the number of individual variables. The thesis is based on four articles published or accepted for publication. They concern propositional dynamic logics, propositional branchingand alternating-time temporal logics, propositional logics of symmetric rela tions, and first-order predicate modal and intuitionistic logics. In all cases, we identify the “minimal,” with regard to the criteria mentioned above, fragments whose satisfiability is as computationally hard as satisfiability for the entire logic.en_ZA
dc.description.librarianMT 2019en_ZA
dc.identifier.urihttps://hdl.handle.net/10539/27933
dc.language.isoenen_ZA
dc.phd.titlePHDen_ZA
dc.titleAlgorithmic properties of modal logics with restricted languagesen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Mikhail_Rybakov-PhD_Thesis.pdf
Size:
854.49 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
ETD Collection