From real-time logic to timed automata

T. Ferrere, O. Maler, D. Ničković, A. Pnueli, Journal of the ACM 66 (2019).

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English

Scopus indexed
Author
Ferrere, ThomasIST Austria ; Maler, Oded; Ničković, Dejan; Pnueli, Amir
Department
Abstract
We show how to construct temporal testers for the logic MITL, a prominent linear-time logic for real-time systems. A temporal tester is a transducer that inputs a signal holding the Boolean value of atomic propositions and outputs the truth value of a formula along time. Here we consider testers over continuous-time Boolean signals that use clock variables to enforce duration constraints, as in timed automata. We first rewrite the MITL formula into a “simple” formula using a limited set of temporal modalities. We then build testers for these specific modalities and show how to compose testers for simple formulae into complex ones. Temporal testers can be turned into acceptors, yielding a compositional translation from MITL to timed automata. This construction is much simpler than previously known and remains asymptotically optimal. It supports both past and future operators and can easily be extended.
Publishing Year
Date Published
2019-05-01
Journal Title
Journal of the ACM
Volume
66
Issue
3
Article Number
19
ISSN
IST-REx-ID

Cite this

Ferrere T, Maler O, Ničković D, Pnueli A. From real-time logic to timed automata. Journal of the ACM. 2019;66(3). doi:10.1145/3286976
Ferrere, T., Maler, O., Ničković, D., & Pnueli, A. (2019). From real-time logic to timed automata. Journal of the ACM, 66(3). https://doi.org/10.1145/3286976
Ferrere, Thomas, Oded Maler, Dejan Ničković, and Amir Pnueli. “From Real-Time Logic to Timed Automata.” Journal of the ACM 66, no. 3 (2019). https://doi.org/10.1145/3286976.
T. Ferrere, O. Maler, D. Ničković, and A. Pnueli, “From real-time logic to timed automata,” Journal of the ACM, vol. 66, no. 3, 2019.
Ferrere T, Maler O, Ničković D, Pnueli A. 2019. From real-time logic to timed automata. Journal of the ACM. 66(3), 19.
Ferrere, Thomas, et al. “From Real-Time Logic to Timed Automata.” Journal of the ACM, vol. 66, no. 3, 19, ACM, 2019, doi:10.1145/3286976.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar