Nominals for Everyone

It has been recognised that the expressivity of description logics benefits from the introduction of non-standard modal operators beyond existential and number restrictions. Such operators support notions such as uncertainty, defaults, agency, obligation, or evidence, whose semantics often lies outside the realm of relational structures. Coalgebraic hybrid logic serves as a unified setting for logics that combine non-standard modal operators and nominals, which allow reasoning about individuals. In this framework, we prove a generic EXPTIME upper bound for concept satisfiability over general TBoxes, which instantiates to novel upper bounds for many individual logics including probabilistic logic with nominals.

Lutz Schröder, Dirk Pattinson, Clemens Kupke