Tractable Fragments of Temporal Sequences of Topological Information
This work addresses theoretical limitations in spatio-temporal reasoning for AI applications, but is incremental as it builds on existing frameworks to identify tractable cases.
The paper tackles the problem of reasoning about qualitative temporal sequences of topological information, showing that no Cartesian subclass containing all basic relations and the universal relation can be decided by algebraic closure, but identifies tractable subclasses by excluding certain relations and formalizing an alternative semantics for sequences on time partitions.
In this paper, we focus on qualitative temporal sequences of topological information. We firstly consider the context of topological temporal sequences of length greater than 3 describing the evolution of regions at consecutive time points. We show that there is no Cartesian subclass containing all the basic relations and the universal relation for which the algebraic closure decides satisfiability. However, we identify some tractable subclasses, by giving up the relations containing the non-tangential proper part relation and not containing the tangential proper part relation. We then formalize an alternative semantics for temporal sequences. We place ourselves in the context of the topological temporal sequences describing the evolution of regions on a partition of time (i.e. an alternation of instants and intervals). In this context, we identify large tractable fragments.