Do You Need Infinite Time?

Do You Need Infinite Time?

Alessandro Artale, Andrea Mazzullo, Ana Ozaki

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1516-1522. https://doi.org/10.24963/ijcai.2019/210

Linear temporal logic over finite traces is used as a formalism for temporal specification in automated planning, process modelling and (runtime) verification. In this paper, we investigate first-order temporal logic over finite traces, lifting some known results to a more expressive setting. Satisfiability in the two-variable monodic fragment is shown to be EXPSPACE-complete, as for the infinite trace case, while it decreases to NEXPTIME when we consider finite traces bounded in the number of instants. This leads to new complexity results for temporal description logics over finite traces. We further investigate satisfiability and equivalences of formulas under a model-theoretic perspective, providing a set of semantic conditions that characterise when the distinction between reasoning over finite and infinite traces can be blurred. Finally, we apply these conditions to planning and verification.
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Geometric, Spatial, and Temporal Reasoning
Knowledge Representation and Reasoning: Knowledge Representation Languages
Knowledge Representation and Reasoning: Logics for Knowledge Representation