Klarman, SMeyer, T2014-10-242014-10-242014-07Complexity of Temporal Query Abduction in DL-Lite. In: 27th International Workshop on Description Logics (DL2014), Vienna, Austria 17-20 July 2014http://ceur-ws.org/Vol-1193/paper_45.pdfhttp://hdl.handle.net/10204/7728Complexity of temporal query abduction in DL-Lite.27th International Workshop on Description Logics (DL2014), Vienna, Austria, 17-20 July 2014. Abstract attached.Temporal query abduction is the problem of hypothesizing a minimal set of temporal data which, given some fixed background knowledge, warrants the entailment of the query. This problem formally underlies a variety of forms of explanatory and diagnostic reasoning in the context of time series data, data streams, or otherwise temporally annotated structured information. In this paper, we consider (temporally ordered) data represented in Description Logics from the popular DL- Lite family and Temporal Query Language, based on the combination of LTL with conjunctive queries. In this defined setting, we study the complexity of temporal query abduction, assuming different restrictions on the problem and minimality criteria for abductive solutions. As a result, we draw several revealing demarcation lines between NP-, DP- and PSpace-complete variants of the problem.enTemporal query abductionDescription logicsTemporal dataConference PresentationKlarman, S., & Meyer, T. (2014). Complexity of temporal query abduction in DL-Lite. http://hdl.handle.net/10204/7728Klarman, S, and T Meyer. "Complexity of temporal query abduction in DL-Lite." (2014): http://hdl.handle.net/10204/7728Klarman S, Meyer T, Complexity of temporal query abduction in DL-Lite; 2014. http://hdl.handle.net/10204/7728 .TY - Conference Presentation AU - Klarman, S AU - Meyer, T AB - Temporal query abduction is the problem of hypothesizing a minimal set of temporal data which, given some fixed background knowledge, warrants the entailment of the query. This problem formally underlies a variety of forms of explanatory and diagnostic reasoning in the context of time series data, data streams, or otherwise temporally annotated structured information. In this paper, we consider (temporally ordered) data represented in Description Logics from the popular DL- Lite family and Temporal Query Language, based on the combination of LTL with conjunctive queries. In this defined setting, we study the complexity of temporal query abduction, assuming different restrictions on the problem and minimality criteria for abductive solutions. As a result, we draw several revealing demarcation lines between NP-, DP- and PSpace-complete variants of the problem. DA - 2014-07 DB - ResearchSpace DP - CSIR KW - Temporal query abduction KW - Description logics KW - Temporal data LK - https://researchspace.csir.co.za PY - 2014 T1 - Complexity of temporal query abduction in DL-Lite TI - Complexity of temporal query abduction in DL-Lite UR - http://hdl.handle.net/10204/7728 ER -