Institute of Theoretical Computer Science Research Projects
Parameterised Complexity of Nonclassical Logics

Parameterised Complexity of Nonclasscial Logics

  • Participants:
  • Duration: April 2014 - February 2018
  • DFG reference number: ME 4279/1-1
List of selected publications

Project Description

According to the current level of knowledge, very little is known about the parameterised complexity of problems in the field of program verification and artificial intelligence. In this context, we want to study model checking problems as well as reasoning problems with respect to their parameterised complexity. Furthermore, we search normal forms in regard of parameterisations that might explain the usually high complexity of such problems.

Sensible Parameterisations

We will focus of benefits from parameterisations in the area of modal as well as nonmonotonic logics. Aiming to improve the knowledge on correlation between parameterisations and concepts in these logics, we will study different approaches here.

Classification of the parameterised complexity of fragments of temporal and nonmonotonic logics

In the last decade, a vast amount of fragments of such logics have been classically classified. The study of parameterisations and acquired knowledge of correlations between modal and nonmonotonic operators with Boolean functions will improve the overall understanding of these concepts. Could similar observations as in propositional logic be made?