Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Tomorrow and All our Yesterdays: MTL Satisfiability over the Integers
verfasst von : Carlo A. Furia, Paola Spoletini
Erschienen in: Theoretical Aspects of Computing - ICTAC 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.