Abstract
We describe a new approach to synthesizing a timed automaton from a set of timed scenarios. The set of scenarios specifies a set of behaviours, i.e., sequences of events that satisfy the time constraints imposed by the scenarios. The language of the constructed automaton is equivalent to that set of behaviours. Every location of the automaton appears in at least one accepting run, and its graph is constructed so as to minimise the number of clocks. The construction allows a new clock allocation algorithm whose cost is linear in the number of edges.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
To keep the presentation compact, we do not allow sharp inequalities [15].
- 2.
By Observation 1, if \(\alpha \in \mathcal {L}_\mathcal {M}\), there is no transition r such that \(\alpha \in born (r) \cap used (r)\). However, this is quite possible for \(\alpha \in \mathcal {L}_{n} \setminus \mathcal {L}_\mathcal {M}\): in that case, the last transition of a path of \(\alpha \) can be the same as the first transition of another path of \(\alpha \).
- 3.
\(\alpha \) may, but need not, be different from \(\alpha '\).
- 4.
In our setting two ranges of the same label can overlap, but cannot be conflicting.
References
Abdulla, P.A., Deneux, J., Ouaknine, J., Worrell, J.: Decidability and complexity results for timed automata via channel machines. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1089–1101. Springer, Heidelberg (2005). https://doi.org/10.1007/11523468_88
Alur, R.: Timed automata. In: Halbwachs, N., Peled, D. (eds.) CAV 1999. LNCS, vol. 1633, pp. 8–22. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48683-6_3
Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183–235 (1994)
Alur, R., Martin, M., Raghothaman, M., Stergiou, C., Tripakis, S., Udupa, A.: Synthesizing finite-state protocols from scenarios and requirements. In: Yahav, E. (ed.) HVC 2014. LNCS, vol. 8855, pp. 75–91. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13338-6_7
An, J., Chen, M., Zhan, B., Zhan, N., Zhang, M.: Learning one-clock timed automata. TACAS 2020. LNCS, vol. 12078, pp. 444–462. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45190-5_25
Baier, C., Bertrand, N., Bouyer, P., Brihaye, T.: When are timed automata determinizable? In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 43–54. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02930-1_4
Bollig, B., Katoen, J.-P., Kern, C., Leucker, M.: Replaying play in and play out: synthesis of design models from scenarios by learning. In: Grumberg, O., Huth, M. (eds.) TACAS 2007. LNCS, vol. 4424, pp. 435–450. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71209-1_33
Clarke Jr., E.M., Grumberg, O., Peled, D.A.: Model Checking. MIT Press, Cambridge (1999)
Damas, C., Lambeau, B., Roucoux, F., van Lamsweerde, A.: Analyzing critical process models through behavior model synthesis. In: Proceedings of the 31st International Conference on Software Engineering, pp. 441–451. IEEE Computer Society (2009)
Giese, H.: Towards scenario-based synthesis for parametric timed automata. In: Proceedings of the 2nd International Workshop on Scenarios and State Machines: Models, Algorithms, and Tools (SCESM), Portland, USA (2003)
Grinchtein, O., Jonsson, B., Leucker, M.: Learning of event-recording automata. Theor. Comput. Sci. 411(47), 4029–4054 (2010)
Lin, S., André, É., Liu, Y., Sun, J., Dong, J.S.: Learning assumptions for compositional verification of timed systems. IEEE Trans. Software Eng. 40(2), 137–153 (2014)
Saeedloei, N., Kluźniak, F.: Clock allocation in timed automata and graph colouring. In: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week), HSCC 2018, pp. 71–80 (2018)
Saeedloei, N., Kluźniak, F.: From scenarios to timed automata. In: Cavalheiro, S., Fiadeiro, J. (eds.) SBMF 2017. LNCS, vol. 10623, pp. 33–51. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70848-5_4
Saeedloei, N., Kluźniak, F.: Timed scenarios: consistency, equivalence and optimization. In: Massoni, T., Mousavi, M.R. (eds.) SBMF 2018. LNCS, vol. 11254, pp. 215–233. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03044-5_14
Saeedloei, N., Kluźniak, F.: Untangling the Graphs of Timed Automata to Streamline the Number of Clocks. https://tigerweb.towson.edu/nsaeedloei/untangling.pdf
Salah, A., Dssouli, R., Lapalme, G.: Compiling real-time scenarios into a timed automaton. In: Kim, M., Chin, B., Kang, S., Lee, D. (eds.) FORTE 2001. IIFIP, vol. 69, pp. 135–150. Springer, Boston, MA (2002). https://doi.org/10.1007/0-306-47003-9_9
Somé, S., Dssouli, R., Vaucher, J.: From scenarios to timed automata: building specifications from users requirements. In: Proceedings of the Second Asia Pacific Software Engineering Conference, pp. 48–57. IEEE Computer Society (1995)
Uchitel, S., Brunet, G., Chechik, M.: Synthesis of partial behavior models from properties and scenarios. IEEE Trans. Softw. Eng. 35(3), 384–406 (2009)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Saeedloei, N., Kluźniak, F. (2020). Synthesizing Clock-Efficient Timed Automata. In: Dongol, B., Troubitsyna, E. (eds) Integrated Formal Methods. IFM 2020. Lecture Notes in Computer Science(), vol 12546. Springer, Cham. https://doi.org/10.1007/978-3-030-63461-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-63461-2_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63460-5
Online ISBN: 978-3-030-63461-2
eBook Packages: Computer ScienceComputer Science (R0)