Deductive Systems and the Decidability Problem for Hybrid Logics
Deductive Systems and the Decidability Problem for Hybrid Logics

Author(s): Michał Zawidzki
Subject(s): Economy
Published by: Wydawnictwo Uniwersytetu Łódzkiego
Keywords: hybrid logics; logic; deductive systems
Summary/Abstract: Hybrid logics are powerful extensions of modal logics, which, roughly speaking, allow for referring to the semantics of the logic by means of syntactic tools. Augmenting standard modal logics with expressions of an additional sort - nominals, and the so-called satisfaction operators caused a spectacular boost to their expressive power. The satisfaction relation, accessibility statements and equality assertions, hitherto only expressible in meta-language, became available within the object language of the logic. A natural question arose: how do these highly expressive logics behave in terms of decidability? How much must we sacrifice to the altar of this increased expressive power? However, whereas the sole origins of hybrid logics can be traced back to the 1960s and the works of Arthur Prior, some additional ”computational” properties of these logics have become a subject of systematic research relatively recently. There has been a lot done since then, though. From the mid-1990s to the present times, a systematic theory of the computational complexity of hybrid logics has been developed by many researchers: Patrick Blackburn, Jerry Seligman, Carlos Areces, Maarten Marx, Thomas Schneider - just to mention a few. Up to now almost all the facts from this area of investigation have been revealed. Theorems placing particular hybrid logics in concrete complexity classes have been established for most of them, defined over most of the well-known frame classes. It seems that not much is left to be done.

• Details
• Contents