{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T01:53:57Z","timestamp":1787882037110,"version":"build-2784847793"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google","award":["PhD Fellowship"],"award-info":[{"award-number":["PhD Fellowship"]}]},{"name":"National Science Foundation","award":["NSF CCF 1901069"],"award-info":[{"award-number":["NSF CCF 1901069"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394783","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"713-727","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["The Complexity of Dynamic Data Race Prediction"],"prefix":"10.1145","author":[{"given":"Umang","family":"Mathur","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana, Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90051-5"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360576"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"key":"e_1_3_2_1_4_1","first-page":"2","article-title":"Membership Problems for Regular and Context-Free Trace","volume":"82","author":"Bertoni A.","year":"1989","unstructured":"A. Bertoni , G. Mauri , and N. Sabadini . 1989 . Membership Problems for Regular and Context-Free Trace Languages. Inf. Comput. 82 , 2 (Aug. 1989), 135--150. https:\/\/doi.org\/10.1016\/0890-5401(89)90051-5 10.1016\/0890-5401(89)90051-5 A. Bertoni, G. Mauri, and N. Sabadini. 1989. Membership Problems for Regular and Context-Free Trace Languages. Inf. Comput. 82, 2 (Aug. 1989), 135--150. https:\/\/doi.org\/10.1016\/0890-5401(89)90051-5","journal-title":"Languages. Inf. Comput."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2001252.2001255"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2414729.2414732"},{"key":"e_1_3_2_1_8_1","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Rolf Niedermeier and Christophe Paul (Eds.)","volume":"126","author":"Bringmann Karl","year":"2019","unstructured":"Karl Bringmann . 2019 . Fine-Grained Complexity Theory (Tutorial) . In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Rolf Niedermeier and Christophe Paul (Eds.) , Vol. 126 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 4:1--4:7. https:\/\/doi.org\/10.4230\/LIPIcs.STACS. 2019.4 10.4230\/LIPIcs.STACS.2019.4 Karl Bringmann. 2019. Fine-Grained Complexity Theory (Tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Rolf Niedermeier and Christophe Paul (Eds.), Vol. 126. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 4:1--4:7. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.4"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158119"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770351.1770387"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_3_2_1_12_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer . https:\/\/doi.org\/10.1007\/978-1-4612-0515-9 10.1007\/978-1-4612-0515-9 Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer. https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_1_13_1","volume-title":"Proc. ACM Program. Lang. 2, POPL, Article Article 25 (Dec.","author":"Emmi Michael","year":"2017","unstructured":"Michael Emmi and Constantin Enea . 2017 . Sound, Complete, and Tractable Linearizability Monitoring for Concurrent Collections . Proc. ACM Program. Lang. 2, POPL, Article Article 25 (Dec. 2017), 27 pages. https:\/\/doi.org\/10.1145\/3158113 10.1145\/3158113 Michael Emmi and Constantin Enea. 2017. Sound, Complete, and Tractable Linearizability Monitoring for Concurrent Collections. Proc. ACM Program. Lang. 2, POPL, Article Article 25 (Dec. 2017), 27 pages. https:\/\/doi.org\/10.1145\/3158113"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '09)","author":"Flanagan Cormac","unstructured":"Cormac Flanagan and Stephen N. Freund . 2009. FastTrack: Efficient and Precise Dynamic Race Detection . In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '09) . ACM, New York, NY, USA, 121--133. https:\/\/doi.org\/10.1145\/1542476.1542490 10.1145\/1542476.1542490 Cormac Flanagan and Stephen N. Freund. 2009. FastTrack: Efficient and Precise Dynamic Race Detection. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '09). ACM, New York, NY, USA, 121--133. https:\/\/doi.org\/10.1145\/1542476.1542490"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594315"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522736"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062374"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_3_2_1_23_1","unstructured":"Umang Mathur Andreas Pavlogiannis and Mahesh Viswanathan. 2020. The Complexity of Dynamic Data Race Prediction. (2020). arXiv:cs.PL\/2004.14931  Umang Mathur Andreas Pavlogiannis and Mahesh Viswanathan. 2020. The Complexity of Dynamic Data Race Prediction. (2020). arXiv:cs.PL\/2004.14931"},{"key":"e_1_3_2_1_24_1","volume-title":"Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel & Distributed Algorithms, M. Cosnard et. al. (Ed.)","author":"Mattern Friedemann","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. Cosnard et. al. (Ed.) . Elsevier Science Publishers B. V. , 215--226. 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. Cosnard et. al. (Ed.). Elsevier Science Publishers B. V., 215--226."},{"key":"e_1_3_2_1_25_1","volume-title":"Advances in Petri Nets","author":"Mazurkiewicz A","year":"1986","unstructured":"A Mazurkiewicz . 1987. Trace Theory . In Advances in Petri Nets 1986 , Part II on Petri Nets : Applications and Relationships to Other Models of Concurrency. Springer-Verlag New York , Inc., 279--324. A Mazurkiewicz. 1987. Trace Theory. In Advances in Petri Nets 1986, Part II on Petri Nets: Applications and Relationships to Other Models of Concurrency. Springer-Verlag New York, Inc., 279--324."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273442.1250738"},{"key":"e_1_3_2_1_28_1","volume-title":"On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions. In In Proceedings of the 1990 International Conference on Parallel Processing. 93--97","author":"Robert","unstructured":"Robert H.B. Netzer and Barton P. Miller. 1990 . On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions. In In Proceedings of the 1990 International Conference on Parallel Processing. 93--97 . Robert H.B. Netzer and Barton P. Miller. 1990. On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions. In In Proceedings of the 1990 International Conference on Parallel Processing. 93--97."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"e_1_3_2_1_30_1","volume-title":"Miller","author":"Netzer Robert Netzer","year":"1989","unstructured":"Robert Netzer Netzer and Barton P . Miller . 1989 . Detecting Data Races in Parallel Program Executions. In In Advances in Languages and Compilers for Parallel Computing, 1990 Workshop. MIT Press , 109--129. Robert Netzer Netzer and Barton P. Miller. 1989. Detecting Data Races in Parallel Program Executions. In In Advances in Languages and Compilers for Parallel Computing, 1990 Workshop. MIT Press, 109--129."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_3_2_1_32_1","volume-title":"Proc. ACM Program. Lang. 4, POPL, Article Article 17 (Dec.","author":"Pavlogiannis Andreas","year":"2019","unstructured":"Andreas Pavlogiannis . 2019 . Fast, Sound, and Effectively Complete Dynamic Race Prediction . Proc. ACM Program. Lang. 4, POPL, Article Article 17 (Dec. 2019), 29 pages. https:\/\/doi.org\/10.1145\/3371085 10.1145\/3371085 Andreas Pavlogiannis. 2019. Fast, Sound, and Effectively Complete Dynamic Race Prediction. Proc. ACM Program. Lang. 4, POPL, Article Article 17 (Dec. 2019), 29 pages. https:\/\/doi.org\/10.1145\/3371085"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/966049.781529"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1889997.1890000"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018","author":"Roemer Jake","year":"1923","unstructured":"Jake Roemer , Kaan Gen\u00e7 , and Michael D. Bond . 2018. High-coverage, Unbounded Sound Predictive Race Detection . In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018 ). ACM, New York, NY, USA, 374--389. https:\/\/doi.org\/10.1145\/3 1923 66.3192385 10.1145\/3192366.3192385 Jake Roemer, Kaan Gen\u00e7, and Michael D. Bond. 2018. High-coverage, Unbounded Sound Predictive Race Detection. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). ACM, New York, NY, USA, 374--389. https:\/\/doi.org\/10.1145\/3192366.3192385"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1986308.1986334"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265927"},{"key":"e_1_3_2_1_38_1","volume-title":"Formal Methods for Open Object-Based Distributed Systems","author":"Sen Koushik","unstructured":"Koushik Sen , Grigore Ro\u015fu , and Gul Agha . 2005. Detecting Errors in Multithreaded Programs by Generalized Predictive Analysis of Executions . In Formal Methods for Open Object-Based Distributed Systems , Martin Steffen and Gianluigi Zavattaro (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 211--226. Koushik Sen, Grigore Ro\u015fu, and Gul Agha. 2005. Detecting Errors in Multithreaded Programs by Generalized Predictive Analysis of Executions. In Formal Methods for Open Object-Based Distributed Systems, Martin Steffen and Gianluigi Zavattaro (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 211--226."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/42190.42277"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103702"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05089-3_17"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2009.56"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Saarbr\u00fccken Germany","acronym":"LICS '20","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"]},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":44,"alternative-id":["10.1145\/3373718.3394783","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394783","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}