{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:22Z","timestamp":1750220242068,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p>Jeffrey D. Ullman and Alfred V. Aho are recipients of the 2020 ACM A.M. Turing award. They were recognized for creating fundamental algorithms and theory underlying programming language implementation and for synthesizing these results and those of others in their highly influential books, which educated generations of computer scientists.<\/jats:p>","DOI":"10.1145\/3490685","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T16:24:29Z","timestamp":1643041469000},"page":"76-91","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Abstractions, their algorithms, and their compilers"],"prefix":"10.1145","volume":"65","author":[{"given":"Alfred","family":"Aho","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Ullman","sequence":"additional","affiliation":[{"name":"Stanford University in Stanford, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aaronson S. Ten semi-grand challenges for quantum computing theory. (2005) https:\/\/www.scottaaronson.com\/writings\/qchallenge.html.  Aaronson S. Ten semi-grand challenges for quantum computing theory. (2005) https:\/\/www.scottaaronson.com\/writings\/qchallenge.html."},{"key":"e_1_2_1_2_1","volume-title":"Doklady Akademii Nauk 146","author":"Adel'son-Vel'skii G.M.","year":"1962","unstructured":"Adel'son-Vel'skii , G.M. and Landis , E.M . An algorithm for organization of information . In Doklady Akademii Nauk 146 ( 1962 ), Russian Academy of Sciences , 263--266. Adel'son-Vel'skii, G.M. and Landis, E.M. An algorithm for organization of information. In Doklady Akademii Nauk 146 (1962), Russian Academy of Sciences, 263--266."},{"key":"e_1_2_1_3_1","first-page":"4","article-title":"Upper and lower bounds on the cost of a map-reduce computation","volume":"6","author":"Afrati F.N.","year":"2013","unstructured":"Afrati , F.N. , Sarma , A.D. , Salihoglu , S. , and Ullman , J.D . Upper and lower bounds on the cost of a map-reduce computation . In Proceedings of the VLDB Endowment 6 , 4 ( 2013 ), 277--288. Afrati, F.N., Sarma, A.D., Salihoglu, S., and Ullman, J.D. Upper and lower bounds on the cost of a map-reduce computation. In Proceedings of the VLDB Endowment 6, 4 (2013), 277--288.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_4_1","volume-title":"Algorithms for Finding Patterns in Strings","author":"Aho","year":"1991","unstructured":"Aho ., A.V. Algorithms for Finding Patterns in Strings . MIT Press , Cambridge, MA, USA ( 1991 ), 255--300. Aho., A.V. Algorithms for Finding Patterns in Strings. MIT Press, Cambridge, MA, USA (1991), 255--300."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1473195.1473196"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/577958"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512928"},{"key":"e_1_2_1_9_1","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A.V.","year":"2006","unstructured":"Aho , A.V. , Lam , M.S. , Sethi , R. , and Ullman , J.D . Compilers: Principles, Techniques, and Tools , 2 nd Edition. Addison-Wesley Longman Publishing Co., Inc. , USA , ( 2006 ). Aho, A.V., Lam, M.S., Sethi, R., and Ullman, J.D. Compilers: Principles, Techniques, and Tools, 2nd Edition. Addison-Wesley Longman Publishing Co., Inc., USA, (2006).","edition":"2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/560992"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808479"},{"key":"e_1_2_1_12_1","unstructured":"Apache Software Foundation. Hadoop.  Apache Software Foundation. Hadoop."},{"volume-title":"Record of the 1970 ACM SIGFIDET Workshop on Data Description and Access, 107--141","author":"Bayer R.","key":"e_1_2_1_13_1","unstructured":"Bayer , R. and McCreight , E.M. Organization and maintenance of large ordered indices . In Record of the 1970 ACM SIGFIDET Workshop on Data Description and Access, 107--141 . Bayer, R. and McCreight, E.M. Organization and maintenance of large ordered indices. In Record of the 1970 ACM SIGFIDET Workshop on Data Description and Access, 107--141."},{"key":"e_1_2_1_14_1","volume-title":"SIGFIDET '74","author":"Chamberlin D.D.","year":"1974","unstructured":"Chamberlin , D.D. and Boyce , R.F . Sequel: A structured English query language . SIGFIDET '74 , Association for Computing Machinery ( 1974 ), 249--264. Chamberlin, D.D. and Boyce, R.F. Sequel: A structured English query language. SIGFIDET '74, Association for Computing Machinery (1974), 249--264."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_16_1","volume-title":"Database Systems","author":"Codd E.F.","year":"1972","unstructured":"Codd , E.F. Relational completeness of database sublanguages . In Database Systems . Prentice-Hall ( 1972 ), 65--98. Codd, E.F. Relational completeness of database sublanguages. In Database Systems. Prentice-Hall (1972), 65--98."},{"key":"e_1_2_1_17_1","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"Dean , J. and Ghemawat , S . MapReduce: Simplified data processing on large clusters . In OSDI ( 2004 ), 137--150. Dean, J. and Ghemawat, S. MapReduce: Simplified data processing on large clusters. In OSDI (2004), 137--150."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/11740.001.0001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321240"},{"key":"e_1_2_1_20_1","volume-title":"Parallel algorithmic techniques for combinatorial computation","author":"Eppstein D.","year":"1988","unstructured":"Eppstein , D. and Galil , Z . Parallel algorithmic techniques for combinatorial computation . Annual Reviews Inc . ( 1988 ), 233--283. Eppstein, D. and Galil, Z. Parallel algorithmic techniques for combinatorial computation. Annual Reviews Inc. (1988), 233--283."},{"key":"e_1_2_1_21_1","volume-title":"Database Systems: The Complete Book","author":"Garcia-Molina H.","year":"2008","unstructured":"Garcia-Molina , H. , Ullman , J.D. , and Widom , J . Database Systems: The Complete Book . Prentice Hall Press , USA ( 2008 ). Garcia-Molina, H., Ullman, J.D., and Widom, J. Database Systems: The Complete Book. Prentice Hall Press, USA (2008)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_23_1","volume-title":"A model of computation for MapReduce","author":"Karlo H.","year":"2010","unstructured":"Karlo , H. , Suri , S. , and Vassilvitskii , S . A model of computation for MapReduce ( 2010 ), 938--948. Karlo, H., Suri, S., and Vassilvitskii, S. A model of computation for MapReduce (2010), 938--948."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512945"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037022"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90426-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/363269.363281"},{"key":"e_1_2_1_29_1","first-page":"4","article-title":"A guide to formal analysis of join processing in massively parallel systems","volume":"45","author":"Koutris P.","year":"2016","unstructured":"Koutris , P. and Suciu , D . A guide to formal analysis of join processing in massively parallel systems . ACM SIGMOD Rec 45 , 4 ( 2016 ), 18--27. Koutris, P. and Suciu, D. A guide to formal analysis of join processing in massively parallel systems. ACM SIGMOD Rec 45, 4 (2016), 18--27.","journal-title":"ACM SIGMOD Rec"},{"key":"e_1_2_1_30_1","volume-title":"Lex---A Lexical Analyzer Generator","author":"Lesk M.E.","year":"1990","unstructured":"Lesk , M.E. and Schmidt , E . Lex---A Lexical Analyzer Generator . W.B. Saunders Company , USA ( 1990 ), 375--387. Lesk, M.E. and Schmidt, E. Lex---A Lexical Analyzer Generator. W.B. Saunders Company, USA (1990), 375--387."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/942572.807045"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_33_1","volume-title":"Next steps in quantum computing: Computer science's role","author":"Martonosi M.","year":"2019","unstructured":"Martonosi M. and Roetteler , M . Next steps in quantum computing: Computer science's role . Computing Community Consortium ( 2019 ). Martonosi M. and Roetteler, M. Next steps in quantum computing: Computer science's role. Computing Community Consortium (2019)."},{"key":"e_1_2_1_34_1","first-page":"1","article-title":"Regular expressions and state graphs for automata","volume":"9","author":"McNaughton R.","year":"1960","unstructured":"McNaughton , R. and Yamada , H . Regular expressions and state graphs for automata . IRE Transactions on Electronic Computers 9 , 1 ( 1960 ), 39--47. McNaughton, R. and Yamada, H. Regular expressions and state graphs for automata. IRE Transactions on Electronic Computers 9, 1 (1960), 39--47.","journal-title":"IRE Transactions on Electronic Computers"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1972505"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.12.0130"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079856.3080256"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2006.4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183895.3183901"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_43_1","first-page":"42","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"2","author":"Turing A.M","year":"1936","unstructured":"Turing , A.M . On computable numbers, with an application to the Entscheidungsproblem . In Proc. London Math. Soc 2 , 42 ( 1936 ), 230--265. Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem. In Proc. London Math. Soc 2, 42 (1936), 230--265.","journal-title":"Proc. London Math. Soc"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_45_1","volume-title":"A graph theoretical Fortran source language analyzer. Bell Laboratories Internal Document","author":"Vyssotsky V.","year":"1963","unstructured":"Vyssotsky , V. and Wegner , P . A graph theoretical Fortran source language analyzer. Bell Laboratories Internal Document ( 1963 ). Vyssotsky, V. and Wegner, P. A graph theoretical Fortran source language analyzer. Bell Laboratories Internal Document (1963)."},{"key":"e_1_2_1_46_1","unstructured":"Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Abstract_data_type. Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Abstract_data_type."},{"key":"e_1_2_1_47_1","unstructured":"Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Bulk_synchronous_parallel. Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Bulk_synchronous_parallel."},{"key":"e_1_2_1_48_1","unstructured":"Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Interface_(Java). Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Interface_(Java)."},{"key":"e_1_2_1_49_1","unstructured":"Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Serverless_computing. Wikipedia 2021. https:\/\/en.wikipedia.org\/wiki\/Serverless_computing."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1118178.1118215"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:29Z","timestamp":1750188629000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,24]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.1145\/3490685"],"URL":"https:\/\/doi.org\/10.1145\/3490685","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2022,1,24]]},"assertion":[{"value":"2022-01-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}