nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Distance on Timed Words and Applications

verfasst von : Eugene Asarin, Nicolas Basset, Aldric Degorre

Erschienen in: Formal Modeling and Analysis of Timed Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce and study a new (pseudo) metric on timed words having several advantages:

it is global: it applies to words having different number of events;
it is realistic and takes into account imprecise observation of timed events; thus it reflects the fact that the order of events cannot be observed whenever they are very close to each other;
it is suitable for quantitative verification of timed systems: we formulate and solve quantitative model-checking and quantitative monitoring in terms of the new distance, with reasonable complexity;
it is suitable for information-theoretical analysis of timed systems: due to its pre-compactness the quantity of information in bits per time unit can be correctly defined and computed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Non-bisimulation Based Behavioral Relations for Markov Automata

Nächstes Kapitel Online Timed Pattern Matching Using Automata

Generally, shared clocks could be considered, but they are not needed in this paper.

As usual in information theory, all logarithms are base 2.

when \(T<b\), the set of interest \(F^\varSigma _{b,T}\) is empty.

Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126, 183–235 (1994). https://doi.org/10.1016/0304-3975(94)90010-8MathSciNetCrossRefMATH

Asarin, E.: Challenges in timed languages: from applied theory to basic theory (column: concurrency). Bull. EATCS 83, 106–120 (2004). https://eatcs.org/images/bulletin/beatcs83.pdfMathSciNetMATH

Asarin, E., Basset, N., Béal, M.P., Degorre, A., Perrin, D.: Toward a timed theory of channel coding. In: Jurdziński, M., Niĉković, D. (eds.) FORMATS 2012. LNCS, vol. 7595, pp. 27–42. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33365-1_4CrossRefMATH

Asarin, E., Basset, N., Degorre, A.: Entropy of regular timed languages. Inf. Comput. 241, 142–176 (2015). https://doi.org/10.1016/j.ic.2015.03.003MathSciNetCrossRefMATH

Asarin, E., Degorre, A.: Volume and entropy of regular timed languages: discretization approach. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 69–83. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04081-8_6CrossRef

Asarin, E., Degorre, A.: Two size measures for timed languages. In: Lodaya, K., Mahajan, M. (eds.) Proceedings of FSTTCS. LIPIcs, vol. 8, pp. 376–387 (2010). https://doi.org/10.4230/LIPIcs.FSTTCS.2010.376

Basset, N.: Timed symbolic dynamics. In: Sankaranarayanan, S., Vicario, E. (eds.) FORMATS 2015. LNCS, vol. 9268, pp. 44–59. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22975-1_4CrossRefMATH

Chatterjee, K., Ibsen-Jensen, R., Majumdar, R.: Edit distance for timed automata. In: Fränzle, M., Lygeros, J. (eds.) Proceedings of HSCC, pp. 303–312. ACM (2014). https://doi.org/10.1145/2562059.2562141

Courcoubetis, C., Yannakakis, M.: Minimum and maximum delay problems in real-time systems. Form. Method. Syst. Des. 1(4), 385–415 (1992). https://doi.org/10.1007/BF00709157CrossRefMATH

10.

Donzé, A., Maler, O.: Robust satisfaction of temporal logic over real-valued signals. In: Chatterjee, K., Henzinger, T.A. (eds.) FORMATS 2010. LNCS, vol. 6246, pp. 92–106. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15297-9_9CrossRefMATH

11.

Gupta, V., Henzinger, T.A., Jagadeesan, R.: Robust timed automata. In: Maler, O. (ed.) HART 1997. LNCS, vol. 1201, pp. 331–345. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0014736CrossRef

12.

Kolmogorov, A., Tikhomirov, V.: \(\varepsilon \)-entropy and \(\varepsilon \)-capacity of sets in function spaces. Uspekhi Mat. Nauk 14(2), 3–86 (1959). Russian, English translation in [15]MathSciNetMATH

13.

Robbins, H.: A remark on Stirling’s formula. Am. Math. Mon. 62(1), 26–29 (1955). https://doi.org/10.2307/2308012MathSciNetCrossRefMATH

14.

Sankur, O., Bouyer, P., Markey, N., Reynier, P.-A.: Robust controller synthesis in timed automata. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013. LNCS, vol. 8052, pp. 546–560. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40184-8_38CrossRef

15.

Shiryayev, A. (ed.): Selected works of A.N. Kolmogorov, vol. 3. Springer, Dordrecht (1993). https://doi.org/10.1007/978-94-017-2973-4CrossRef

Titel: Distance on Timed Words and Applications
verfasst von: Eugene Asarin
Nicolas Basset
Aldric Degorre
Verlag: Springer International Publishing
Buch: Formal Modeling and Analysis of Timed Systems
Print ISBN: 978-3-030-00150-6

Electronic ISBN: 978-3-030-00151-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-00151-3_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner