Hybridizing Interval Temporal Logics: The First Step

No. 1: Thirty-First AAAI Conference On Artificial Intelligence

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 31

Student Abstract Track

Temporal reasoning is one of the main topics investigated within the field of Artificial Intelligence. Formal methods for temporal reasoning arouse interest of researchers from both theoretical and practical point of view. Such methods enable modelling and studying human-like reasoning mechanisms, thus constituting a valuable tool in cognitive science, philosophy, and linguistics. On the other hand, temporal reasoning formalisms have a number of potential practical applications, e.g., in task scheduling, action planning, and temporal databases. Temporal reasoning methods may be divided into point-based and interval-based depending on the type of the considered primitive ontological objects. My work revolves around the latter type of methods which seem to be more human-like and more suitable for such applications as continuous process modelling. My main result is that the satisfiability problem in a hybridized fragment of Halpern-Shoham logic in which formulas are in a form of conjunction of Horn clauses and only box modal operators are allowed (diamond operators are disallowed) is NP-complete over reflexive, as well as over irreflexive and dense time frames. Before hybridization this fragment was P-complete over such time structures.

10.1609/aaai.v31i1.11108