Advertisement
Published in:
2008 | OriginalPaper | Chapter
Tomorrow and All our Yesterdays: MTL Satisfiability over the Integers
Authors : Carlo A. Furia, Paola Spoletini
Published in: Theoretical Aspects of Computing - ICTAC 2008
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We investigate the satisfiability problem for metric temporal logic (MTL) with both past and future operators over linear discrete bi-infinite time models isomorphic to the integer numbers, where time is unbounded both in the future and in the past. We provide a technique to reduce satisfiability over the integers to satisfiability over the well-known mono-infinite time model of natural numbers, and we show how to implement the technique through an automata-theoretic approach. We also prove that MTL satisfiability over the integers is
EXPSPACE
-complete, hence the given algorithm is optimal in the worst case.