{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T02:27:20Z","timestamp":1784255240098,"version":"3.55.0"},"reference-count":104,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            While current bug detection techniques for concurrent software focus on unearthing low-level issues such as data races or deadlocks, they often fall short of discovering more intricate temporal behaviours that can arise even in the absence of such low-level issues. In this paper, we focus on the problem of dynamically analysing concurrent software against high-level temporal specifications such as LTL. Existing techniques for runtime monitoring against such specifications are primarily designed for sequential software and remain inadequate in the presence of concurrency \u2014 violations may be observed only in intricate thread interleavings, requiring many re-runs of the underlying software in conjunction with the analysis. Towards this, we study the problem of\n            <jats:italic toggle=\"yes\">predictive runtime monitoring<\/jats:italic>\n            , inspired by the analogous problem of\n            <jats:italic toggle=\"yes\">predictive data race detection<\/jats:italic>\n            studied extensively recently. The predictive runtime monitoring question asks, given an execution\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>\u03c3<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , if it can be soundly\n            <jats:italic toggle=\"yes\">reordered<\/jats:italic>\n            to expose violations of a specification. In general, this problem may become easily intractable when either the specifications or the notion of reorderings used is complex.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we focus on specifications that are given in regular languages. Our notion of reorderings is\n            <jats:italic toggle=\"yes\">trace equivalence<\/jats:italic>\n            , where an execution is considered a reordering of another if it can be obtained from the latter by successively commuting adjacent independent actions. We first show that, even in this simplistic setting, the problem of predictive monitoring admits a super-linear lower bound of\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>O<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mi>\u03b1<\/mml:mi>\n                  <\/mml:msup>\n                  <mml:mo>)<\/mml:mo>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , where\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>n<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            is the number of events in the execution, and\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>\u03b1<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            is a parameter describing the degree of commutativity, and typically corresponds to the number of threads in the execution. As a result, predictive runtime monitoring even in this setting is unlikely to be efficiently solvable, unlike in the non-predictive setting where the problem can be checked using a deterministic finite automaton (and thus, a constant-space streaming linear-time algorithm).\n          <\/jats:p>\n          <jats:p>\n            Towards this, we identify a sub-class of regular languages, called\n            <jats:italic toggle=\"yes\">pattern languages<\/jats:italic>\n            (and their extension\n            <jats:italic toggle=\"yes\">generalized pattern languages<\/jats:italic>\n            ). Pattern languages can naturally express specific ordering of some number of (labelled) events, and have been inspired by popular empirical hypotheses underlying many concurrency bug detection approaches such as the \u201csmall bug depth\u201d hypothesis. More importantly, we show that for pattern (and generalized pattern) languages, the predictive monitoring problem can be solved using a constant-space streaming linear-time algorithm. We implement and evaluate our algorithm\n            <jats:sc>PatternTrack<\/jats:sc>\n            on benchmarks from the literature and show that it is effective in monitoring large-scale applications.\n          <\/jats:p>","DOI":"10.1145\/3632915","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"2191-2225","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Predictive Monitoring against Pattern Regular Languages"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-0214-3462","authenticated-orcid":false,"given":"Zhendong","family":"Ang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7610-0660","authenticated-orcid":false,"given":"Umang","family":"Mathur","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"2023. AntLRWorks. https:\/\/github.com\/antlr\/antlrworks. [Online; accessed 24-October-2023]."},{"key":"e_1_3_1_3_1","unstructured":"2023. exp4j. https:\/\/github.com\/fasseg\/exp4j. [Online; accessed 24-October-2023]."},{"key":"e_1_3_1_4_1","unstructured":"2023. JFreeChart. https:\/\/github.com\/jfree\/jfreechart. [Online; accessed 24-October-2023]."},{"key":"e_1_3_1_5_1","unstructured":"2023. Logstash Logback Encoder. https:\/\/github.com\/logfellow\/logstash-logback-encoder. [Online; accessed 24-October-2023]."},{"key":"e_1_3_1_6_1","unstructured":"2023. ZeroMQ log4j appender. https:\/\/github.com\/lusis\/zmq-appender. [Online; accessed 24-October-2023]."},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535845"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314649"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678838"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1995.380415"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24730-2_35"},{"key":"e_1_3_1_12_1","unstructured":"Zhendong Ang and Umang Mathur. 2003a Predictive Monitoring against Pattern Regular Languages. arxiv:2310.14611 https:\/\/arxiv.org\/abs\/231014611"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","unstructured":"Zhendong Ang and Umang Mathur. 2023b. Predictive Monitoring against Pattern Regular Languages. https:\/\/doi.org\/10.5281\/zenodo.8424626 10.5281\/zenodo.8424626 Artifact.","DOI":"10.5281\/zenodo.8424626"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/STVR.281"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11678779_15"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90051-5"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594323"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276514"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2001.932515"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/582419.582440"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1736020.1736040"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380367"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3468549"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73368-3_27"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368088.1368119"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_9"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/5397.5399"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926432"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945468"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70545-1_8"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00768-2_14"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2393596.2393651"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.84874"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806672.1806674"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377492.1377495"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375618"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040315"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781169"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575729"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2540128.2540252"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180225"},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2015.96"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594315"},{"key":"e_1_3_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1999.1574"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00017"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2012.6227231"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542489"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276516"},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132767"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000017719.43755.7C"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062374"},{"key":"e_1_3_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236025"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498711"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314609"},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995674"},{"key":"e_1_3_1_61_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CONCUR.2021.16"},{"key":"e_1_3_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970356"},{"key":"e_1_3_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30206-3_12"},{"key":"e_1_3_1_64_1","unstructured":"Umang Mathur. 2023. RAPID. https:\/\/github.com\/umangm\/rapid Accessed: 2023-10-25."},{"key":"e_1_3_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_3_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507734"},{"key":"e_1_3_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394783"},{"key":"e_1_3_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434317"},{"key":"e_1_3_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378475"},{"key":"e_1_3_1_70_1","first-page":"215","volume-title":"Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel & Distributed Algorithms","author":"Mattern Friedemann","year":"1989","unstructured":"Friedemann Mattern. 1989. Virtual Time and Global States of Distributed Systems. In Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel & Distributed Algorithms, M. Cosnardet al. (Ed.). Elsevier Science Publishers B. V., 215\u2013226."},{"key":"e_1_3_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-17906-2_30"},{"key":"e_1_3_1_72_1","unstructured":"Robert McNaughton and Seymour Papert. 1971. Counter-Free Automata."},{"key":"e_1_3_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10515-010-0063-Y"},{"key":"e_1_3_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE-SEIP52600.2021.00038"},{"key":"e_1_3_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71410-1_2"},{"key":"e_1_3_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_3_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446748"},{"issue":"1985","key":"e_1_3_1_78_1","first-page":"56","article-title":"Regular behaviour of concurrent systems","volume":"27","author":"Ochma\u0144ski Edward","year":"1985","unstructured":"Edward Ochma\u0144ski. 1985. Regular behaviour of concurrent systems. Bull. EATCS 27 (1985), 56\u201367.","journal-title":"Bull. EATCS"},{"key":"e_1_3_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360606"},{"key":"e_1_3_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371085"},{"key":"e_1_3_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_3_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2003.1213513"},{"key":"e_1_3_1_83_1","unstructured":"Jake Roemer and Michael D. Bond. 2019. Online Set-Based Dynamic Analysis for Sound Predictive Race Detection. CoRR abs\/1907.08337 (2019). arXiv:1907.08337 http:\/\/arxiv.org\/abs\/1907.08337"},{"key":"e_1_3_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192385"},{"key":"e_1_3_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385993"},{"key":"e_1_3_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10515-005-6205-Y"},{"key":"e_1_3_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44881-0_35"},{"key":"e_1_3_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188720"},{"key":"e_1_3_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20398-5_23"},{"key":"e_1_3_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265927"},{"key":"e_1_3_1_91_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"e_1_3_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/11494881_14"},{"key":"e_1_3_1_93_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)81051-X"},{"key":"e_1_3_1_94_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10009-005-0192-Y"},{"key":"e_1_3_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35632-2_16"},{"key":"e_1_3_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_3_1_97_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34188-5_11"},{"key":"e_1_3_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103702"},{"key":"e_1_3_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/582034.582042"},{"key":"e_1_3_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882291.1882300"},{"key":"e_1_3_1_101_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591291"},{"key":"e_1_3_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111067"},{"key":"e_1_3_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287654"},{"key":"e_1_3_1_104_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0188"},{"key":"e_1_3_1_105_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96142-2_20"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:06:49Z","timestamp":1751659609000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":104,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632915"],"URL":"https:\/\/doi.org\/10.1145\/3632915","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}