On coarser interval temporal logics
In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely , not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen's relations are a guarantee of decidability, as we prove that the second variant, namely , remains undecidable in all interesting cases.
The article is avaible in full version at this link: https://www.sciencedirect.com/science/article/pii/S0004370218305964#br0050
Keywords
Authors
- Department of Applied Mathematics, University of Malaga, Spain
- Department of Statistics and Operational Research, University of Murcia, Spain
- Department of Computer Science, University of Verona, Italy
- - Department of Mathematics and Computer Science, University of Ferrara, Italy
- Department of Mathematics, Computer Science, and Physics, University of Udine, Italy
Received 16 April 2017, Revised 7 September 2018, Accepted 20 September 2018, Available online 17 October 2018 on
Artificial Intelligence
Artificial Intelligence is a magazine that began to be published in 1970, and is now generally considered the world's leading magazine for artificial intelligence, especially as regards theoretical and foundational aspects (impact factor of 3.034, impact factor at 5 years 4.156).
Professor Guido Sciavicco, in collaboration with three Italian and Spanish researchers, and a graduate in Computer Science of our university, has signed this article. It concerns aspects of computability and complexity of Interval periodic logics, long considered an instrument of undoubted utility for the representation of knowledge. Among other results, this work has shown that using inaccurate temporal relations (less expressive than the classical ones, but still sufficiently expressive to have a practical value), it is possible to construct a formal temporal language for which there is a relatively efficient algorithm to establish if a certain statement is true. Among the most interesting aspects of this work, we highlight the possibility of using these relationships in the extraction of knowledge, in particular from data that present complex interactions between time series. The authors, in alphabetical order, are: Emilio Muñoz-Velasco (University of Malaga), Mercedes Pelegrìn (University of Murcia), Pietro Sala (University of Verona), Guido Sciavicco (University of Ferrara), and Ionel Eduard Stan (graduate at the University of Ferrara, today a master's student at the University of Udine).
