Ferrere, ThomasIST Austria ; Maler, Oded; Ničković, Dejan; Pnueli, Amir
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.
Journal of the ACM
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.