{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:31Z","timestamp":1750309291621,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Bo\u011fazi\u00e7i Research Fund","award":["FRI-454"],"award-info":[{"award-number":["FRI-454"]}]},{"name":"Agence Nationale de Recherche"},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"crossref","award":["CyPhAI"],"award-info":[{"award-number":["CyPhAI"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>The rise of machine learning and cloud technologies has led to a remarkable influx of data within modern cyber-physical systems. However, extracting meaningful information from this data has become a significant challenge due to its volume and complexity. Timed pattern matching has emerged as a powerful specification-based runtime verification and temporal data analysis technique to address this challenge.<\/jats:p>\n          <jats:p>In this paper, we provide a comprehensive tutorial on timed pattern matching that ranges from the underlying algebra and pattern specification languages to performance analyses and practical case studies. Analogous to textual pattern matching, timed pattern matching is the task of finding all time periods within temporal behaviors of cyber-physical systems that match a predefined pattern. Originally we introduced and solved several variants of the problem using the name of match sets, which has evolved into the concept of timed relations over the past decade. Here we first formalize and present the algebra of timed relations as a standalone mathematical tool to solve the pattern matching problem of timed pattern specifications. In particular, we show how to use the algebra of timed relations to solve the pattern matching problem for timed regular expressions and metric compass logic in a unified manner. We experimentally demonstrate that our timed pattern matching approach performs and scales well in practice. We further provide in-depth insights into the similarities and fundamental differences between monitoring and matching problems as well as regular expressions and temporal logic formulas. Finally, we illustrate the practical application of timed pattern matching through two case studies, which show how to extract structured information from temporal datasets obtained via simulations or real-world observations. These results and examples show that timed pattern matching is a rigorous and efficient technique in developing and analyzing cyber-physical systems.<\/jats:p>","DOI":"10.1145\/3645114","type":"journal-article","created":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T10:19:00Z","timestamp":1707560340000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Elements of Timed Pattern Matching"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5090-1769","authenticated-orcid":false,"given":"Dogan","family":"Ulus","sequence":"first","affiliation":[{"name":"Bo\u01e7azi\u00e7i University, Istanbul, Turkey"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5199-3143","authenticated-orcid":false,"given":"Thomas","family":"Ferr\u00e8re","sequence":"additional","affiliation":[{"name":"Imagination Technologies, Kings Langley, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7983-2202","authenticated-orcid":false,"given":"Eugene","family":"Asarin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, CNRS, IRIF, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5468-0396","authenticated-orcid":false,"given":"Dejan","family":"Nickovic","sequence":"additional","affiliation":[{"name":"AIT Austrian Institute of Technology, Vienna, Austria"}]},{"given":"Oded","family":"Maler","sequence":"additional","affiliation":[{"name":"VERIMAG, CNRS, Grenoble, France"}]}],"member":"320","published-online":{"date-parts":[[2024,6,10]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho Alfred V.","year":"1986","unstructured":"Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley. https:\/\/www.worldcat.org\/oclc\/12285707"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"e_1_3_2_4_2","first-page":"10","volume-title":"Proceedings of the International Conference on Engineering of Complex Computer Systems, ICECCS","author":"Andr\u00e9 \u00c9tienne","year":"2018","unstructured":"\u00c9tienne Andr\u00e9, Ichiro Hasuo, and Masaki Waga. 2018. Offline timed pattern matching under uncertainty. In Proceedings of the International Conference on Engineering of Complex Computer Systems, ICECCS. IEEE Computer Society, 10\u201320. DOI:10.1109\/ICECCS2018.2018.00010"},{"key":"e_1_3_2_5_2","first-page":"160","volume-title":"Proceedings of the Symposium on Logic in Computer Science (LICS)","author":"Asarin Eugene","year":"1997","unstructured":"Eugene Asarin, Paul Caspi, and Oded Maler. 1997. A Kleene theorem for timed automata. In Proceedings of the Symposium on Logic in Computer Science (LICS). IEEE, 160\u2013171. DOI:10.1109\/LICS.1997.614944"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506151"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-030-85037-1_1","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"12860","author":"Asarin Eugene","year":"2021","unstructured":"Eugene Asarin, Thomas Ferr\u00e8re, Dejan Nickovic, and Dogan Ulus. 2021. On the complexity of timed pattern matching. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 12860. Springer, 1\u201317. DOI:10.1007\/978-3-030-85037-1_2"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-319-65765-3_12","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"10419","author":"Asarin Eugene","year":"2017","unstructured":"Eugene Asarin, Oded Maler, Dejan Nickovic, and Dogan Ulus. 2017. Combining the temporal and epistemic dimensions for MTL monitoring. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 10419. Springer, 207\u2013223. DOI:10.1007\/978-3-319-65765-3_12"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-319-65765-3_11","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"10419","author":"Bakhirkin Alexey","year":"2017","unstructured":"Alexey Bakhirkin, Thomas Ferr\u00e8re, Oded Maler, and Dogan Ulus. 2017. On the quantitative semantics of regular expressions over real-valued signals. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 10419. Springer, 189\u2013206. DOI:10.1007\/978-3-319-65765-3_11"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-3-030-00151-3_13","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"11022","author":"Bakhirkin Alexey","year":"2018","unstructured":"Alexey Bakhirkin, Thomas Ferr\u00e8re, Dejan Nickovic, Oded Maler, and Eugene Asarin. 2018. Online timed pattern matching using automata. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 11022. Springer, 215\u2013232. DOI:10.1007\/978-3-030-00151-3_13"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-52559-9_62","volume-title":"Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness: REX Workshop, Mook, The Netherlands May 29\u2013June 2, 1989 Proceedings","author":"Barringer Howard","year":"1990","unstructured":"Howard Barringer, Michael Fisher, Dov Gabbay, Graham Gough, and Richard Owens. 1990. METATEM: A framework for programming in temporal logic. In Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness: REX Workshop, Mook, The Netherlands May 29\u2013June 2, 1989 Proceedings. Springer, 94\u2013129. 10.1007\/3-540-52559-9_62"},{"key":"e_1_3_2_12_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-75632-5","volume-title":"Lectures on Runtime Verification \u2014 Introductory and Advanced Topics","author":"Bartocci Ezio","year":"2018","unstructured":"Ezio Bartocci and Yli\u00e8s Falcone (Eds.). 2018. Lectures on Runtime Verification \u2014 Introductory and Advanced Topics. Lecture Notes in Computer Science, Vol. 10457. Springer. DOI:10.1007\/978-3-319-75632-5"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-75632-5_1"},{"key":"e_1_3_2_14_2","first-page":"260","volume-title":"FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings","author":"Bauer Andreas","year":"2006","unstructured":"Andreas Bauer, Martin Leucker, and Christian Schallhart. 2006. Monitoring of real-time properties. In FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings. 260\u2013272. DOI:10.1007\/11944836_25"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.75415"},{"key":"e_1_3_2_16_2","volume-title":"Canonical Expressions in Boolean Algebra","author":"Blake Archie","year":"1938","unstructured":"Archie Blake. 1938. Canonical Expressions in Boolean Algebra. Ph.D. Dissertation. University of Chicago."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1109\/ICDE.2001.914855","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE)","author":"B\u00f6rzs\u00f6nyi Stephan","year":"2001","unstructured":"Stephan B\u00f6rzs\u00f6nyi, Donald Kossmann, and Konrad Stocker. 2001. The Skyline operator. In Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, 421\u2013430. DOI:10.1109\/ICDE.2001.914855"},{"key":"e_1_3_2_18_2","first-page":"695","volume-title":"Proceedings of the European Conference on Artificial Intelligence (ECAI) (Frontiers in Artificial Intelligence and Applications)","volume":"215","author":"Bresolin Davide","year":"2010","unstructured":"Davide Bresolin, Dario Della Monica, Valentin Goranko, Angelo Montanari, and Guido Sciavicco. 2010. Metric propositional neighborhood logics: Expressiveness, decidability, and undecidability. In Proceedings of the European Conference on Artificial Intelligence (ECAI) (Frontiers in Artificial Intelligence and Applications), Vol. 215. IOS Press, 695\u2013700. DOI:10.3233\/978-1-60750-606-5-695"},{"key":"e_1_3_2_19_2","volume-title":"SVA: The Power of Assertions in SystemVerilog","author":"Cerny Eduard","year":"2014","unstructured":"Eduard Cerny, Surrendra Dudani, John Havlicek, and Dmitry Korchemny. 2014. SVA: The Power of Assertions in SystemVerilog. Springer."},{"key":"e_1_3_2_20_2","first-page":"3735","volume-title":"Proceedings of the Conference on Language Resources and Evaluation (LREC)","author":"Chang Angel X.","year":"2012","unstructured":"Angel X. Chang and Christopher D. Manning. 2012. SUTime: A library for recognizing and normalizing time expressions. In Proceedings of the Conference on Language Resources and Evaluation (LREC). European Language Resources Association (ELRA), 3735\u20133740. http:\/\/www.lrec-conf.org\/proceedings\/lrec2012\/summaries\/284.html"},{"issue":"5","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0020-0190(91)90122-X","article-title":"A calculus of durations","volume":"40","author":"Chaochen Zhou","year":"1991","unstructured":"Zhou Chaochen, Charles Anthony Richard Hoare, and Anders P. Ravn. 1991. A calculus of durations. Inform. Process. Lett. 40, 5 (1991), 269\u2013276.","journal-title":"Inform. Process. Lett."},{"key":"e_1_3_2_22_2","first-page":"74","volume-title":"Proceedings of the Real-Time Systems Symposium - 1991, San Antonio, Texas, USA, December 1991","author":"Chodrow Sarah E.","year":"1991","unstructured":"Sarah E. Chodrow, Farnam Jahanian, and Marc Donner. 1991. Run-time monitoring of real-time systems. In Proceedings of the Real-Time Systems Symposium - 1991, San Antonio, Texas, USA, December 1991. 74\u201383. DOI:10.1109\/REAL.1991.160360"},{"key":"e_1_3_2_23_2","first-page":"845","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","author":"Monica Dario Della","year":"2011","unstructured":"Dario Della Monica, Valentin Goranko, Angelo Montanari, and Guido Sciavicco. 2011. Expressiveness of the interval logics of Allen\u2019s relations on the class of all linear orders: complete classification. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). AAAI, 845\u2013850. https:\/\/www.aaai.org\/ocs\/index.php\/IJCAI\/IJCAI11\/paper\/viewPaper\/3273"},{"issue":"105","key":"e_1_3_2_24_2","article-title":"Interval temporal logics: A journey","volume":"3","author":"Monica Dario Della","year":"2013","unstructured":"Dario Della Monica, Valentin Goranko, Angelo Montanari, and Guido Sciavicco. 2013. Interval temporal logics: A journey. Bulletin of the EATCS 3, 105 (2013). http:\/\/smtp.eatcs.org\/index.php\/beatcs\/article\/download\/94\/90","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/363848.363863"},{"key":"e_1_3_2_26_2","first-page":"197","volume-title":"Proceedings of the Conference on Computer Aided Verification (CAV) (LNCS)","volume":"407","author":"Dill David L.","year":"1989","unstructured":"David L. Dill. 1989. Timing assumptions and verification of finite-state concurrent systems. In Proceedings of the Conference on Computer Aided Verification (CAV) (LNCS), Vol. 407. Springer, 197\u2013212. DOI:10.1007\/3-540-52148-8_17"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1145\/302405.302672","volume-title":"Proceedings of the Conference on Software Engineering","author":"Dwyer Matthew B.","year":"1999","unstructured":"Matthew B. Dwyer, George S. Avrunin, and James C. Corbett. 1999. Patterns in property specifications for finite-state verification. In Proceedings of the Conference on Software Engineering. 411\u2013420."},{"key":"e_1_3_2_28_2","volume-title":"A Practical Introduction to PSL","author":"Eisner Cindy","year":"2007","unstructured":"Cindy Eisner and Dana Fisman. 2007. A Practical Introduction to PSL. Springer."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/978-3-319-21668-3_19","volume-title":"Proceedings of the Conference on Computer Aided Verification (CAV) (LNCS)","volume":"9207","author":"Ferr\u00e8re Thomas","year":"2015","unstructured":"Thomas Ferr\u00e8re, Oded Maler, Dejan Nickovic, and Dogan Ulus. 2015. Measuring with timed patterns. In Proceedings of the Conference on Computer Aided Verification (CAV) (LNCS), Vol. 9207. Springer, 322\u2013337. DOI:10.1007\/978-3-319-21668-3_19"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.11.004"},{"key":"e_1_3_2_31_2","first-page":"163","volume-title":"Proceedings of the Symposium on Principles of Programming Languages (POPL)","author":"Gabbay Dov","year":"1980","unstructured":"Dov Gabbay, Amir Pnueli, Saharon Shelah, and Jonathan Stavi. 1980. On the temporal analysis of fairness. In Proceedings of the Symposium on Principles of Programming Languages (POPL). ACM, 163\u2013173. DOI:10.1145\/567446.567462"},{"key":"e_1_3_2_32_2","first-page":"412","volume-title":"16th IEEE International Conference on Automated Software Engineering (ASE 2001), 26-29 November 2001, Coronado Island, San Diego, CA, USA","author":"Giannakopoulou Dimitra","year":"2001","unstructured":"Dimitra Giannakopoulou and Klaus Havelund. 2001. Automata-based verification of temporal properties on running programs. In 16th IEEE International Conference on Automated Software Engineering (ASE 2001), 26-29 November 2001, Coronado Island, San Diego, CA, USA. 412\u2013416. DOI:10.1109\/ASE.2001.989841"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115351"},{"key":"e_1_3_2_34_2","first-page":"342","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems, 8th International Conference, TACAS 2002, held as part of the Joint European Conference on Theory and Practice of Software, ETAPS 2002, Grenoble, France, April 8-12, 2002, Proceedings","author":"Havelund Klaus","year":"2002","unstructured":"Klaus Havelund and Grigore Rosu. 2002. Synthesizing monitors for safety properties. In Tools and Algorithms for the Construction and Analysis of Systems, 8th International Conference, TACAS 2002, held as part of the Joint European Conference on Theory and Practice of Software, ETAPS 2002, Grenoble, France, April 8-12, 2002, Proceedings. 342\u2013356. DOI:10.1007\/3-540-46002-0_24"},{"key":"e_1_3_2_35_2","first-page":"155","volume-title":"Proceedings of the Conference on Formal Methods in Computer-Aided Design (FMCAD)","author":"Havlicek John","year":"2011","unstructured":"John Havlicek and Scott Little. 2011. Realtime regular expressions for analog and mixed-signal assertions. In Proceedings of the Conference on Formal Methods in Computer-Aided Design (FMCAD). 155\u2013162."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1206049.1206056"},{"key":"e_1_3_2_37_2","first-page":"189","volume-title":"Automatic Verification Methods for Finite State Systems, International Workshop, Grenoble, France, June 12-14, 1989, Proceedings","author":"Jard Claude","year":"1989","unstructured":"Claude Jard and Thierry J\u00e9ron. 1989. On-line model checking for finite linear temporal logic specifications. In Automatic Verification Methods for Finite State Systems, International Workshop, Grenoble, France, June 12-14, 1989, Proceedings. 189\u2013196. DOI:10.1007\/3-540-52148-8_16"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995674"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_3_2_40_2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-540-30206-3_12","volume-title":"Proceedings of the Conference on Formal Techniques, Modeling and Analysis of Timed and Fault-Tolerant Systems (FORMATS\/FTRTFT)","volume":"3253","author":"Maler Oded","year":"2004","unstructured":"Oded Maler and Dejan Nickovic. 2004. Monitoring temporal properties of continuous signals. In Proceedings of the Conference on Formal Techniques, Modeling and Analysis of Timed and Fault-Tolerant Systems (FORMATS\/FTRTFT). LNCS, Vol. 3253. Springer, 152\u2013166. DOI:10.1007\/978-3-540-30206-3_12"},{"key":"e_1_3_2_41_2","first-page":"14:1\u201314:13","volume-title":"Proceedings of the 26th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2023, San Antonio, TX, USA, May 9-12, 2023","author":"Mambakam Akshay","year":"2023","unstructured":"Akshay Mambakam, Eugene Asarin, Nicolas Basset, and Thao Dang. 2023. Pattern matching and parameter identification for parametric timed regular expressions. In Proceedings of the 26th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2023, San Antonio, TX, USA, May 9-12, 2023. 14:1\u201314:13. DOI:10.1145\/3575870.3587115"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3101715"},{"key":"e_1_3_2_43_2","first-page":"111","volume-title":"Proceedings of the Conference on Concurrency Theory (CONCUR)","author":"Moszkowski Ben","year":"1984","unstructured":"Ben Moszkowski. 1984. Executing temporal logic programs. In Proceedings of the Conference on Concurrency Theory (CONCUR). 111\u2013130. 10.1007\/3-540-15670-4_6"},{"issue":"1","key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1075\/li.30.1.03nad","article-title":"A survey of named entity recognition and classification","volume":"30","author":"Nadeau David","year":"2007","unstructured":"David Nadeau and Satoshi Sekine. 2007. A survey of named entity recognition and classification. Lingvisticae Investigationes 30, 1 (2007), 3\u201326.","journal-title":"Lingvisticae Investigationes"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147660"},{"key":"e_1_3_2_46_2","first-page":"63","volume-title":"2019 IEEE International Conference on Systems, Man and Cybernetics, SMC","author":"Narayan Apurva","year":"2019","unstructured":"Apurva Narayan and Sebastian Fischmeister. 2019. Mining time for timed regular specifications. In 2019 IEEE International Conference on Systems, Man and Cybernetics, SMC. IEEE, 63\u201369. DOI:10.1109\/SMC.2019.8914490"},{"key":"e_1_3_2_47_2","volume-title":"Checking Timed and Hybrid Properties: Theory and Applications","author":"Nickovic Dejan","year":"2008","unstructured":"Dejan Nickovic. 2008. Checking Timed and Hybrid Properties: Theory and Applications. Ph.D. Dissertation. Universit\u00e9 Joseph Fourier. https:\/\/tel.archives-ouvertes.fr\/tel-00411957"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"e_1_3_2_49_2","article-title":"Specifying and deciding quantified discrete-time duration calculus formulae using DCVALID","author":"Pandya Paritosh K.","year":"2001","unstructured":"Paritosh K. Pandya. 2001. Specifying and deciding quantified discrete-time duration calculus formulae using DCVALID. Real-Time Tools, RTTOOLS (2001).","journal-title":"Real-Time Tools, RTTOOLS"},{"key":"e_1_3_2_50_2","first-page":"679","volume-title":"Handbook of Formal Languages","author":"Pin Jean-Eric","year":"1997","unstructured":"Jean-Eric Pin. 1997. Syntactic semigroups. In Handbook of Formal Languages. Springer, 679\u2013746."},{"key":"e_1_3_2_51_2","first-page":"387","volume-title":"Proceedings of Intelligent Transportation Systems Conference (ITSC)","author":"Romera Eduardo","year":"2016","unstructured":"Eduardo Romera, Luis M. Bergasa, and Roberto Arroyo. 2016. Need data for driver behaviour analysis? Presenting the public UAH-DriveSet. In Proceedings of Intelligent Transportation Systems Conference (ITSC). IEEE, 387\u2013392. DOI:10.1109\/ITSC.2016.7795584"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3040259"},{"key":"e_1_3_2_53_2","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1998","unstructured":"A. Schrijver. 1998. Theory of Linear and Integer Programming. Wiley."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_2_55_2","first-page":"397","volume-title":"1st IEEE International Conference on Engineering of Complex Computer Systems (ICECCS\u201995), November 6-10, 1995, Fort Lauderdale, Florida, USA","author":"Tsai Grace","year":"1995","unstructured":"Grace Tsai, M. Insall, and Bruce M. McMillin. 1995. Ensuring the satisfaction of a temporal specification at run-time. In 1st IEEE International Conference on Engineering of Complex Computer Systems (ICECCS\u201995), November 6-10, 1995, Fort Lauderdale, Florida, USA. 397\u2013404. DOI:10.1109\/ICECCS.1995.479365"},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-319-63387-9_16","volume-title":"Proceedings of the Conference on Computer Aided Verification (CAV) (LNCS)","volume":"10426","author":"Ulus Dogan","year":"2017","unstructured":"Dogan Ulus. 2017. Montre: A tool for monitoring timed regular expressions. In Proceedings of the Conference on Computer Aided Verification (CAV) (LNCS), Vol. 10426. Springer, 329\u2013335. DOI:10.1007\/978-3-319-63387-9_16"},{"key":"e_1_3_2_57_2","article-title":"Online monitoring of metric temporal logic using sequential networks","author":"Ulus Dogan","year":"2019","unstructured":"Dogan Ulus. 2019. Online monitoring of metric temporal logic using sequential networks. arXiv preprint arXiv:1901.00175 (2019).","journal-title":"arXiv preprint arXiv:1901.00175"},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/978-3-030-32079-9_25","volume-title":"Proceedings of the Conference on Runtime Verification (RV)","author":"Ulus Dogan","year":"2019","unstructured":"Dogan Ulus. 2019. Timescales: A benchmark generator for MTL monitoring tools. In Proceedings of the Conference on Runtime Verification (RV). Springer, 402\u2013412. 10.1007\/978-3-030-32079-9_25"},{"key":"e_1_3_2_59_2","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/978-3-319-10512-3_16","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"8711","author":"Ulus Dogan","year":"2014","unstructured":"Dogan Ulus, Thomas Ferr\u00e8re, Eugene Asarin, and Oded Maler. 2014. Timed pattern matching. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 8711. Springer, 222\u2013236. DOI:10.1007\/978-3-319-10512-3_16"},{"key":"e_1_3_2_60_2","first-page":"736","volume-title":"Proceedings of the Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (LNCS)","volume":"9636","author":"Ulus Dogan","year":"2016","unstructured":"Dogan Ulus, Thomas Ferr\u00e8re, Eugene Asarin, and Oded Maler. 2016. Online timed pattern matching using derivatives. In Proceedings of the Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (LNCS), Vol. 9636. Springer, 736\u2013751. DOI:10.1007\/978-3-662-49674-9_47"},{"key":"e_1_3_2_61_2","first-page":"167","volume-title":"Proceedings of the Conference on Hybrid Systems: Computation and Control (HSCC)","author":"Ulus Dogan","year":"2018","unstructured":"Dogan Ulus and Oded Maler. 2018. Specifying timed patterns using temporal logic. In Proceedings of the Conference on Hybrid Systems: Computation and Control (HSCC). ACM, 167\u2013176. DOI:10.1145\/3178126.3178129"},{"key":"e_1_3_2_62_2","volume-title":"The Logic of Time. A Model-Theoretic Investigation into the Varieties of Temporal Ontology and Temporal Discourse","author":"Benthem Johan van","year":"1991","unstructured":"Johan van Benthem. 1991. The Logic of Time. A Model-Theoretic Investigation into the Varieties of Temporal Ontology and Temporal Discourse. Springer."},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635589"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29662-9_1"},{"key":"e_1_3_2_65_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-319-44878-7_8","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"9884","author":"Waga Masaki","year":"2016","unstructured":"Masaki Waga, Takumi Akazaki, and Ichiro Hasuo. 2016. A Boyer-Moore type algorithm for timed pattern matching. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 9884. Springer, 121\u2013139. DOI:10.1007\/978-3-319-44878-7_8"},{"key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/978-3-319-65765-3_13","volume-title":"Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS)","volume":"10419","author":"Waga Masaki","year":"2017","unstructured":"Masaki Waga, Ichiro Hasuo, and Kohei Suenaga. 2017. Efficient online timed pattern matching by automata-based skipping. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems (FORMATS) (LNCS), Vol. 10419. Springer, 224\u2013243. DOI:10.1007\/978-3-319-65765-3_13"},{"key":"e_1_3_2_67_2","first-page":"14","volume-title":"Proceedings of the Workshop on Monitoring and Testing of Cyber-Physical Systems (MT-CPS)","author":"Waga Masaki","year":"2018","unstructured":"Masaki Waga, Ichiro Hasuo, and Kohei Suenaga. 2018. MONAA: A tool for timed pattern matching with automata-based acceleration. In Proceedings of the Workshop on Monitoring and Testing of Cyber-Physical Systems (MT-CPS). IEEE, 14\u201315. DOI:10.1109\/MT-CPS.2018.00014"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(03)00013-3"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3645114","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3645114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:28Z","timestamp":1750291408000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3645114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":67,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3645114"],"URL":"https:\/\/doi.org\/10.1145\/3645114","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2022-06-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}