Search

Interval temporal logics formalize reasoning about interval structures over (usually) linearly ordered domains, where time intervals are the primitive ontological entities and truth of formulae is defined relative to time intervals, rather than time points. In this paper, we introduce and study Metric Propositional Neighborhood Logic (MPNL) over natural numbers. MPNL features two modalities referring, respectively, to an interval that is “met by” the current one and to an interval that “meets” the current one, plus an infinite set of length constraints, regarded as atomic propositions, to constrain the lengths of intervals. We argue that MPNL can be successfully used in different areas of artificial intelligence to combine qualitative and quantitative interval temporal reasoning, thus providing a viable alternative to well-established logical frameworks such as Duration Calculus. We show that MPNL is decidable in double exponential time and expressively complete with respect to a well-defined subfragment of the two-variable fragment FO2[N, =

Interval temporal logics provide a natural framework for temporal reasoning about interval structures over linearly ordered domains, where intervals are taken as the primitive ontological entities. In this paper, we identify all fragments of Halpern and Shoham's interval temporal logic HS whose finite satisfiability problem is decidable. We classify them in terms of both relative expressive power and complexity. We show that there are exactly 62 expressively-different decidable fragments, whose complexity ranges from NP-complete to non-primitive recursive (all other HS fragments have been already shown to be undecidable).

Temporal dataset evaluation is the problem of establishing to what extent a set of temporal data (histories) complies with a given temporal condition. Checking interval temporal logic formulas against a finite model has been recently proposed, and proved successful, as a tool to solve such a problem. In this paper, we address the problem of checking interval temporal logic specifications, supporting interval length constraints, against infinite, finitely representable models, and we show the applicability of the resulting procedure to the evaluation of incomplete temporal datasets viewed as finite prefixes of ultimately-periodic histories. © 2019, EasyChair. All rights reserved.

Temporal reasoning plays an important role in artificial intelligence. Temporal logics provide a natural framework for its formalization and implementation. A standard way of enhancing the expressive power of temporal logics is to replace their unidimensional domain by a multidimensional one. In particular, such a dimensional increase can be exploited to obtain spatial counterparts of temporal logics. Unfortunately, it often involves a blow up in complexity, possibly losing decidability. In this paper, we propose a spatial generalization of the decidable metric interval temporal logic RPNL+INT, called Directional Area Calculus (DAC). DAC features two modalities, that respectively capture (possibly empty) rectangles to the north and to the east of the current one, and metric operators, to constrain the size of the current rectangle. We prove the decidability of the satisfiability problem for DAC, when interpreted over frames built on natural numbers, and we analyze its complexity. In addition, we consider a weakened version of DAC, called WDAC, which is expressive enough to capture meaningful qualitative and quantitative spatial properties and computationally better.

The validity/satisfiability problem for most propositional interval temporal logics is (highly) undecidable, under very weak assumptions on the class of interval structures in which they are interpreted. That, in particular, holds for most fragments of Halpern and Shoham's interval modal logic HS. Still, decidability is the rule for the fragments of HS with only one modal operator, based on an Allen's relation. In this paper, we show that the logic O of the Overlap relation, when interpreted over discrete linear orderings, is an exception. The proof is based on a reduction from the undecidable octant tiling problem. This is one of the sharpest undecidability result for fragments of HS.

Interval temporal logics (ITLs) are logics for reasoning about temporal statements expressed over intervals, i.e., periods of time. The most famous ITL studied so far is Halpern and Shoham's HS, which is the logic of the thirteen Allen's interval relations. Unfortunately, HS and most of its fragments have an undecidable satisfiability problem. This discouraged the research in this area until recently, when a number non-trivial decidable ITLs have been discovered. This paper is a contribution towards the complete classification of all different fragments of HS. We consider different combinations of the interval relations Begins, After, Later and their inverses Abar, Bbar, and Lbar. We know from previous works that the combination ABBbarAbar is decidable only when finite domains are considered (and undecidable elsewhere), and that ABBbar is decidable over the natural numbers. We extend these results by showing that decidability of ABBar can be further extended to capture the language ABBbarLbar, which lays in between ABBar and ABBbarAbar, and that turns out to be maximal w.r.t decidability over strongly discrete linear orders (e.g. finite orders, the naturals, the integers). We also prove that the proposed decision procedure is optimal with respect to the complexity class.

The management of qualitative spatial information is an important research area in computer science and AI. Modal logic provides a natural framework for the formalization and implementation of qualitative spatial reasoning. Unfortunately, when directional relations are considered, modal logic systems for spatial reasoning usually turn out to be undecidable (often even not recursively enumerable). In this paper, we give a first example of a decidable modal logic for spatial reasoning with directional relations, called Weak Spatial Propositional Neighborhood Logic (WSpPNL for short). WSpPNL features two modalities, respectively an east modality and a north modality, to deal with non-empty rectangles over *** ×***. We first show the NEXPTIME-completeness of WSpPNL, then we develop an optimal tableau method for it.

Interval temporal logics are based on interval structures over linearly (or partially) ordered domains, where time intervals, rather than time instants, are the primitive ontological entities. In this paper we introduce and study Right Propositional Neighborhood Logic over natural numbers with integer constraints for interval lengths, which is a propositional interval temporal logic featuring a modality for the `right neighborhood' relation between intervals and explicit integer constraints for interval lengths. We prove that it has the bounded model property with respect to ultimately periodic models and is therefore decidable. In addition, we provide an EXPSPACE procedure for satisfiability checking and we prove EXPSPACE-hardness by a reduction from the exponential corridor tiling problem.

In this paper we study the definability and decidability of binary predicates for time granularity in monadic languages interpreted over finitely and infinitely layered structures. We focus our attention on the equi-level (respectively equi-column) predicate constraining two time points to belong to the same layer (respectively column) and on the horizontal (respectively vertical) successor predicate relating a time point to its successor within a given layer (respectively column). We give a number of positive and negative results by reduction to/from a wide spectrum of decidable/undecidable problems.

Motivated by two industrial use cases that involve detecting events of interest in (asynchronous) time series from sensors in manufacturing rigs and gas turbines, we design an expressive rule language DslD equipped with interval aggregate functions (such as weighted average over a time interval), Allen's interval relations and various metric constructs. We demonstrate how to model events in the uses cases in terms of DslD programs. We show that answering DslD queries in our use cases can be reduced to evaluating SQL queries. Our experiments with the use cases, carried out on the Apache Spark system, show that such SQL queries scale well on large real-world datasets.