{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T05:56:30Z","timestamp":1785304590483,"version":"3.55.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319657646","type":"print"},{"value":"9783319657653","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-65765-3_13","type":"book-chapter","created":{"date-parts":[[2017,8,2]],"date-time":"2017-08-02T09:08:38Z","timestamp":1501664918000},"page":"224-243","source":"Crossref","is-referenced-by-count":24,"title":["Efficient Online Timed Pattern Matching by Automata-Based Skipping"],"prefix":"10.1007","author":[{"given":"Masaki","family":"Waga","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ichiro","family":"Hasuo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kohei","family":"Suenaga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,3]]},"reference":[{"issue":"2","key":"13_CR1","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0304-3975(94)90010-8","volume":"126","author":"R Alur","year":"1994","unstructured":"Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183\u2013235 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Henzinger, T.A.: Back to the future: towards a theory of timed regular languages. In: 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24\u201327 October 1992, pp. 177\u2013186. IEEE Computer Society (1992)","DOI":"10.1109\/SFCS.1992.267774"},{"issue":"2","key":"13_CR3","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/506147.506151","volume":"49","author":"E Asarin","year":"2002","unstructured":"Asarin, E., Caspi, P., Maler, O.: Timed regular expressions. J. ACM 49(2), 172\u2013206 (2002)","journal-title":"J. ACM"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-36577-X_18","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"G Behrmann","year":"2003","unstructured":"Behrmann, G., Bouyer, P., Fleury, E., Larsen, K.G.: Static guard analysis in timed automata verification. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 254\u2013270. Springer, Heidelberg (2003). doi: 10.1007\/3-540-36577-X_18"},{"issue":"3","key":"13_CR5","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/s10009-005-0190-0","volume":"8","author":"G Behrmann","year":"2006","unstructured":"Behrmann, G., Bouyer, P., Larsen, K.G., Pel\u00e1nek, R.: Lower and upper bounds in zone-based abstractions of timed automata. STTT 8(3), 204\u2013215 (2006)","journal-title":"STTT"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Bombara, G., Vasile, C.I., Penedo, F., Yasuoka, H., Belta, C.: A decision tree approach to data classification using signal temporal logic. In: Abate, A., Fainekos, G.E. (eds.) HSCC 2016, Vienna, Austria, April 12\u201314, 2016, pp. 1\u201310. ACM (2016)","DOI":"10.1145\/2883817.2883843"},{"issue":"10","key":"13_CR7","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"issue":"3","key":"13_CR8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.5626\/JCSE.2016.10.3.75","volume":"10","author":"S Chen","year":"2016","unstructured":"Chen, S., Sokolsky, O., Weimer, J., Lee, I.: Data-driven adaptive safety monitoring using virtual subjects in medical cyber-physical systems: a glucose control case study. JCSE 10(3), 75\u201384 (2016)","journal-title":"JCSE"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/3-540-52148-8_17","volume-title":"Automatic Verification Methods for Finite State Systems","author":"DL Dill","year":"1990","unstructured":"Dill, D.L.: Timing assumptions and verification of finite-state concurrent systems. In: Sifakis, J. (ed.) CAV 1989. LNCS, vol. 407, pp. 197\u2013212. Springer, Heidelberg (1990). doi: 10.1007\/3-540-52148-8_17"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"DSouza, D., Matteplackel, R.: A clock-optimal hierarchical monitoring automaton construction for mitl. Technical report (2013)","DOI":"10.1007\/978-3-642-32943-2_2"},{"issue":"2","key":"13_CR11","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/2431211.2431212","volume":"45","author":"S Faro","year":"2013","unstructured":"Faro, S., Lecroq, T.: The exact online string matching problem: a review of the most recent results. ACM Comput. Surv. 45(2), 13:1\u201313:42 (2013)","journal-title":"ACM Comput. Surv."},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-319-21668-3_19","volume-title":"Computer Aided Verification","author":"T Ferr\u00e8re","year":"2015","unstructured":"Ferr\u00e8re, T., Maler, O., Ni\u010dkovi\u0107, D., Ulus, D.: Measuring with timed patterns. In: Kroening, D., P\u0103s\u0103reanu, C.S. (eds.) CAV 2015. LNCS, vol. 9207, pp. 322\u2013337. Springer, Cham (2015). doi: 10.1007\/978-3-319-21668-3_19"},{"issue":"4","key":"13_CR13","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1016\/j.jda.2006.11.004","volume":"5","author":"F Franek","year":"2007","unstructured":"Franek, F., Jennings, C.G., Smyth, W.F.: A simple fast hybrid pattern-matching algorithm. J. Discrete Algorithms 5(4), 682\u2013695 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-642-14295-6_15","volume-title":"Computer Aided Verification","author":"F Herbreteau","year":"2010","unstructured":"Herbreteau, F., Srivathsan, B., Walukiewicz, I.: Efficient emptiness check for timed b\u00fcchi automata. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol. 6174, pp. 148\u2013161. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14295-6_15"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-319-11164-3_15","volume-title":"Runtime Verification","author":"H-M Ho","year":"2014","unstructured":"Ho, H.-M., Ouaknine, J., Worrell, J.: Online monitoring of metric temporal logic. In: Bonakdarpour, B., Smolka, S.A. (eds.) RV 2014. LNCS, vol. 8734, pp. 178\u2013192. Springer, Cham (2014). doi: 10.1007\/978-3-319-11164-3_15"},{"key":"13_CR16","unstructured":"Hoxha, B., Abbas, H., Fainekos, G.E.: Benchmarks for temporal logic requirements for automotive systems. In: Frehse, G., Althoff, M. (eds.) 1st and 2nd International Workshop on Applied veRification for Continuous and Hybrid Systems, ARCH@CPSWeek 2014, Berlin, Germany, April 14, 2014 \/ ARCH@CPSWeek 2015, EPiC Series in Computing,Seattle, WA, USA, April 13, 2015, vol. 34, pp. 25\u201330. EasyChair (2014)"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Jin, X., Deshmukh, J.V., Kapinski, J., Ueda, K., Butts, K.R.: Powertrain control verification benchmark. In: Fr\u00e4nzle M., Lygeros, J. (eds.) HSCC 2014, Berlin, Germany, April 15\u201317, 2014, pp. 253\u2013262. ACM (2014)","DOI":"10.1145\/2562059.2562140"},{"key":"13_CR18","unstructured":"Kane A.: Runtime monitoring for safety-critical embedded systems. Ph.D. thesis, Carnegie Mellon University, USA (2015)"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-319-23820-3_7","volume-title":"Runtime Verification","author":"A Kane","year":"2015","unstructured":"Kane, A., Chowdhury, O., Datta, A., Koopman, P.: A case study on runtime monitoring of an autonomous research vehicle (ARV) system. In: Bartocci, E., Majumdar, R. (eds.) RV 2015. LNCS, vol. 9333, pp. 102\u2013117. Springer, Cham (2015). doi: 10.1007\/978-3-319-23820-3_7"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-24310-3_16","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"DR Kini","year":"2011","unstructured":"Kini, D.R., Krishna, S.N., Pandya, P.K.: On construction of safety signal automata for $$MITL[\\,\\cal{U},\\,\\cal{S}]$$ using temporal projections. In: Fahrenberg, U., Tripakis, S. (eds.) FORMATS 2011. LNCS, vol. 6919, pp. 225\u2013239. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-24310-3_16"},{"issue":"2","key":"13_CR21","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/11867340_20","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"O Maler","year":"2006","unstructured":"Maler, O., Nickovic, D., Pnueli, A.: From MITL to timed automata. In: Asarin, E., Bouyer, P. (eds.) FORMATS 2006. LNCS, vol. 4202, pp. 274\u2013289. Springer, Heidelberg (2006). doi: 10.1007\/11867340_20"},{"key":"13_CR23","unstructured":"The MathWorks Inc, Natick, MA, USA. Simulink User\u2019s Guide (2015)"},{"key":"13_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-642-15297-9_13","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"D Ni\u010dkovi\u0107","year":"2010","unstructured":"Ni\u010dkovi\u0107, D., Piterman, N.: From Mtl to deterministic timed automata. In: Chatterjee, K., Henzinger, T.A. (eds.) FORMATS 2010. LNCS, vol. 6246, pp. 152\u2013167. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-15297-9_13"},{"key":"13_CR25","unstructured":"Pure Programming Language. https:\/\/purelang.bitbucket.io"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Raimondi, F., Skene, J., Emmerich, W.: Efficient online monitoring of web-service slas. In: Harrold, M.J., Murphy, G.C. (eds.) Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2008, Atlanta, Georgia, USA, November 9\u201314, 2008, pp. 170\u2013180. ACM (2008)","DOI":"10.1145\/1453101.1453125"},{"issue":"3","key":"13_CR27","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s10703-013-0199-z","volume":"44","author":"T Reinbacher","year":"2014","unstructured":"Reinbacher, T., F\u00fcgger, M., Brauer, J.: Runtime verification of embedded real-time systems. Formal Meth. Syst. Des. 44(3), 203\u2013239 (2014)","journal-title":"Formal Meth. Syst. Des."},{"issue":"8","key":"13_CR28","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/79173.79184","volume":"33","author":"D Sunday","year":"1990","unstructured":"Sunday, D.: A very fast substring search algorithm. Commun. ACM 33(8), 132\u2013142 (1990)","journal-title":"Commun. ACM"},{"key":"13_CR29","unstructured":"Ulus, D.: Montre: a tool for monitoring timed regular expressions. CoRR, abs\/1605.05963 (2016)"},{"key":"13_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-319-10512-3_16","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"D Ulus","year":"2014","unstructured":"Ulus, D., Ferr\u00e8re, T., Asarin, E., Maler, O.: Timed pattern matching. In: Legay, A., Bozga, M. (eds.) FORMATS 2014. LNCS, vol. 8711, pp. 222\u2013236. Springer, Cham (2014). doi: 10.1007\/978-3-319-10512-3_16"},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/978-3-662-49674-9_47","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"D Ulus","year":"2016","unstructured":"Ulus, D., Ferr\u00e8re, T., Asarin, E., Maler, O.: Online timed pattern matching using derivatives. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 736\u2013751. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49674-9_47"},{"key":"13_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-319-44878-7_8","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"M Waga","year":"2016","unstructured":"Waga, M., Akazaki, T., Hasuo, I.: A boyer-moore type algorithm for timed pattern matching. In: Fr\u00e4nzle, M., Markey, N. (eds.) FORMATS 2016. LNCS, vol. 9884, pp. 121\u2013139. Springer, Cham (2016). doi: 10.1007\/978-3-319-44878-7_8"},{"key":"13_CR33","unstructured":"Waga, M., Hasuo I., Suenaga, K.: Code that Accompanies \u201cEfficient Online Timed Pattern Matching by Automata-Based Skipping\u201d. https:\/\/github.com\/MasWag\/timed-pattern-matching"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Waga, M., Hasuo, I., Suenaga K.: Efficient Online Timed Pattern Matching by Automata-Based Skipping. CoRR, abs\/1706.09174 (2017)","DOI":"10.1007\/978-3-319-65765-3_13"},{"issue":"2\u20133","key":"13_CR35","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0167-6423(03)00013-3","volume":"48","author":"BW Watson","year":"2003","unstructured":"Watson, B.W., Watson, R.E.: A boyer-moore-style algorithm for regular expression pattern matching. Sci. Comput. Program. 48(2\u20133), 99\u2013117 (2003)","journal-title":"Sci. Comput. Program."}],"container-title":["Lecture Notes in Computer Science","Formal Modeling and Analysis of Timed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-65765-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T19:58:01Z","timestamp":1750795081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-65765-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319657646","9783319657653"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-65765-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}