Conservative Extensions and Satisfiability in Fragments of First-Order Logic : Complexity and Expressive Power

http://nbn-resolving.de/urn:nbn:de:gbv:46-00106704-11
https://elib.suub.uni-bremen.de/peid=D00106704
urn:nbn:de:gbv:46-00106704-11
Martel, Mauricio
2018
Universität Bremen: Informatik/Mathematik
Dissertation
Conservative Extensions, Satisfiability, Expressive Power, Fragments of First-Order Logic
In this thesis, we investigate the decidability and computational complexity of (deductive) conservative extensions in expressive fragments of first-order logic, such as two-variable and guarded fragments. Moreover, we also investigate the complexity of (query) conservative extensions in Horn description logics with inverse roles. Aditionally, we investigate the computational complexity of the satisfiability problem in the unary negation fragment of first-order logic extended with regular path expressions. Besides complexity results, we also study the expressive power of relation-changing modal logics. In particular, we provide translations intto hybrid logic and compare their expressive power using appropriate notions of bisimulations.
DDC
000
2018.09.11/11:09:44
Conservative Extensions and Satisfiability in Fragments of First-Order Logic : Complexity and Expressive Power
[RefWorks] [Bibtex ]
[EndNote ] [RefMan(RIS) ]