From MTL to deterministic timed automata

D. Nickovic, N. Piterman, in:, T.A. Henzinger, K. Chatterjee (Eds.), Springer, 2010, pp. 152–167.

Download
OA IST-2012-49-v1+1_From_MTL_to_deterministic_timed_automata.pdf 249.79 KB

Conference Paper | Published | English

Scopus indexed
Author
Editor
Henzinger, Thomas A.; Chatterjee, Krishnendu
Department
Series Title
LNCS
Abstract
In this paper we propose a novel technique for constructing timed automata from properties expressed in the logic mtl, under bounded-variability assumptions. We handle full mtl and include all future operators. Our construction is based on separation of the continuous time monitoring of the input sequence and discrete predictions regarding the future. The separation of the continuous from the discrete allows us to determinize our automata in an exponential construction that does not increase the number of clocks. This leads to a doubly exponential construction from mtl to deterministic timed automata, compared with triply exponential using existing approaches. We offer an alternative to the existing approach to linear real-time model checking, which has never been implemented. It further offers a unified framework for model checking, runtime monitoring, and synthesis, in an approach that can reuse tools, implementations, and insights from the discrete setting.
Publishing Year
Date Published
2010-09-08
Volume
6246
Page
152 - 167
Conference
FORMATS: Formal Modeling and Analysis of Timed Systems
Conference Location
Klosterneuburg, Austria
Conference Date
2010-09-08 – 2010-09-10
IST-REx-ID

Cite this

Nickovic D, Piterman N. From MTL to deterministic timed automata. In: Henzinger TA, Chatterjee K, eds. Vol 6246. Springer; 2010:152-167. doi:10.1007/978-3-642-15297-9_13
Nickovic, D., & Piterman, N. (2010). From MTL to deterministic timed automata. In T. A. Henzinger & K. Chatterjee (Eds.) (Vol. 6246, pp. 152–167). Presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, Klosterneuburg, Austria: Springer. https://doi.org/10.1007/978-3-642-15297-9_13
Nickovic, Dejan, and Nir Piterman. “From MTL to Deterministic Timed Automata.” edited by Thomas A. Henzinger and Krishnendu Chatterjee, 6246:152–67. Springer, 2010. https://doi.org/10.1007/978-3-642-15297-9_13.
D. Nickovic and N. Piterman, “From MTL to deterministic timed automata,” presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, Klosterneuburg, Austria, 2010, vol. 6246, pp. 152–167.
Nickovic D, Piterman N. 2010. From MTL to deterministic timed automata. FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS, vol. 6246. 152–167.
Nickovic, Dejan, and Nir Piterman. From MTL to Deterministic Timed Automata. Edited by Thomas A. Henzinger and Krishnendu Chatterjee, vol. 6246, Springer, 2010, pp. 152–67, doi:10.1007/978-3-642-15297-9_13.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
b0ca5f5fbe8a3d20ccbc6f51a344a459


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar