{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:02Z","timestamp":1755906002524,"version":"3.44.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>Complex Event Recognition (CER) establishes a relevant solution for processing streams of events, giving users timely information. CER systems detect patterns in real-time, producing complex events and generating responses to them. In these tasks, time is a first-class citizen. Indeed, the time-sequence model distinguishes CER from other solutions, like data stream management systems. Surprisingly, until now, time constraints are usually included in CER query languages and models in a restricted way, and we still lack an understanding of the expressiveness and of efficient algorithms concerning this crucial feature: time.<\/jats:p>\n          <jats:p>This work studies CER under time constraints regarding its query language, computational models, and streaming evaluation algorithms. We start by introducing an extension of Complex Event Logic (CEL), called timed CEL, with simple time operators. We show that timed CEL aids in modeling CER query languages in practice, serving as a proxy to study the expressive power of such languages under time constraints. For this purpose, we introduce an automata model for studying timed CEL, called timed Complex Event Automata (timed CEA). This model extends the existing CEA model with clocks, combining CEA and timed automata in a single model. We show that timed CEL and timed CEA are equally expressive, giving the first characterization of CER query languages under time constraints. Then, we move towards understanding the efficient evaluation of timed CEA over streams concerning its determinization and efficient algorithms. We present a class of timed CEA that are closed under determinization; furthermore, we show that this class contains swg-queries, an expressive class of CER queries recently introduced by Kleest-Mei\u00dfner et al. Finally, we present a streaming evaluation algorithm with constant update time and output-linear delay for evaluating deterministic monotonic timed CEA with a single clock, which have only less equal or greater equal comparisons.<\/jats:p>","DOI":"10.1145\/3725231","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-17","source":"Crossref","is-referenced-by-count":0,"title":["Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-1147-9764","authenticated-orcid":false,"given":"Juli\u00e1n","family":"Garc\u00eda","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile and IMFD, Santiago, Chile"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0832-116X","authenticated-orcid":false,"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile and IMFD, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/1376616.1376634"},{"key":"e_1_2_1_2_1","volume-title":"Pearson Education India","author":"Aho A. V.","year":"1974","unstructured":"A. V. Aho and J. E. Hopcroft. The design and analysis of computer algorithms. Pearson Education India, 1974."},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1016\/0304-3975(94)90010-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/S0304-3975(97)00173-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/506147.506151"},{"issue":"18","key":"e_1_2_1_6_1","first-page":"447","article-title":"Controller synthesis for timed automata","volume":"31","author":"Asarin E.","year":"1998","unstructured":"E. Asarin, O. Maler, A. Pnueli, and J. Sifakis. Controller synthesis for timed automata. IFAC Proceedings Vols., 31(18):447--452, 1998.","journal-title":"IFAC Proceedings"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/11874683_11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1007\/978-3-642-02930-1_4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/3034786.3034789"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1080\/24751839.2017.1347763"},{"issue":"9","key":"e_1_2_1_11_1","first-page":"1951","article-title":"CORE: a complex event recognition engine","volume":"15","author":"Bucchi M.","year":"2022","unstructured":"M. Bucchi, A. Grez, A. Quintana, C. Riveros, and S. Vansummeren. CORE: a complex event recognition engine. VLDB, 15(9):1951--1964, 2022.","journal-title":"VLDB"},{"key":"e_1_2_1_12_1","first-page":"12","volume-title":"RTSS","author":"Chakraborty S.","unstructured":"S. Chakraborty, L. T. Phan, and P. Thiagarajan. Event count automata: A state-based model for stream processing systems. In RTSS, pages 12--pp. IEEE, 2005."},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/j.jss.2012.03.056"},{"key":"e_1_2_1_14_1","volume-title":"Processing flows of information: From data stream to complex event processing. ACM Computing Surveys (CSUR), 44(3):1--62","author":"Cugola G.","year":"2012","unstructured":"G. Cugola and A. Margara. Processing flows of information: From data stream to complex event processing. ACM Computing Surveys (CSUR), 44(3):1--62, 2012."},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/11687238_38"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/11867340_14"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_2_1_18_1","volume-title":"Complex event recognition under time constraints: towards a formal framework for efficient query evaluation. CoRR, abs\/2504.00723","author":"Garc\u00eda J.","year":"2025","unstructured":"J. Garc\u00eda and C. Riveros. Complex event recognition under time constraints: towards a formal framework for efficient query evaluation. CoRR, abs\/2504.00723, 2025."},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1007\/s00778-019-00557-w"},{"key":"e_1_2_1_20_1","volume-title":"Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs\/2206.13851","author":"Grandjean E.","year":"2022","unstructured":"E. Grandjean and L. Jachiet. Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs\/2206.13851, 2022."},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1007\/s00453-022-01025-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/3485463"},{"key":"e_1_2_1_23_1","volume-title":"CONCUR","volume":"243","author":"Henzinger T. A.","year":"2022","unstructured":"T. A. Henzinger, K. Lehtinen, and P. Totzke. History-deterministic timed automata. In CONCUR, volume 243, 2022."},{"key":"e_1_2_1_24_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICDT","author":"Kleest-Mei\u00dfner S.","year":"2022","unstructured":"S. Kleest-Mei\u00dfner, R. Sattler, M. L. Schmid, N. Schweikardt, and M. Weidlich. Discovering event queries from traces: Laying foundations for subsequence-queries with wildcards and gap-size constraints. In ICDT, volume 220 of LIPIcs, pages 18:1--18:21, 2022."},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1007\/BF01995674"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/11587552_13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1007\/s11241-017-9271-x"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/32.464548"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/3514221.3526145"},{"key":"e_1_2_1_30_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICDT","author":"Riveros M.","year":"2022","unstructured":"M. Mu noz and C. Riveros. Streaming enumeration on nested documents. In ICDT, volume 220 of LIPIcs, pages 19:1--19:18, 2022."},{"issue":"1","key":"e_1_2_1_31_1","first-page":"80","article-title":"GRETA: graph-based real-time event trend aggregation","volume":"11","author":"Poppe O.","year":"2017","unstructured":"O. Poppe, C. Lei, E. A. Rundensteiner, and D. Maier. GRETA: graph-based real-time event trend aggregation. VLDB, 11(1):80--92, 2017.","journal-title":"VLDB"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/3452021.3458325"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/2448496.2448498"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1007\/978-3-540-85778-5_7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1007\/s00778-021-00668-3"},{"key":"e_1_2_1_36_1","volume-title":"AMW","author":"Ugarte M.","year":"2018","unstructured":"M. Ugarte and S. Vansummeren. On the difference between complex event processing and dynamic query evaluation. In AMW, 2018."},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1007\/s00778-022-00778-6"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:44Z","timestamp":1755904724000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725231"],"URL":"https:\/\/doi.org\/10.1145\/3725231","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}