Computational Complexity of Fragments of Halpern-Shoham Logic


Main Results:


My Results:

Figure (a) depicts computational complexity over reflexive orders. Figure (b) is for irreflexive and dense orders.


Open Problems:
  • Computational complexity of:
    •  over reflexive and dense frames with punctual intervals (it is not even known if it is decidable);
    •  (it is not even known if it is decidable);
    •  over reflexive frames (it is NLogSpace-hard and in NP);
    •  where L is a modal logic K, T, K4, or S4 (they are NLogSpace-hard and in P).
  • Which fragments of HS enable to express nominals and satisfaction operators?

Materials: