{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:04:25Z","timestamp":1767236665239,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"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":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            We describe an automata-theoretic approach for the competitive analysis of\n            <jats:italic>online algorithms<\/jats:italic>\n            . Our approach is based on\n            <jats:italic>weighted automata<\/jats:italic>\n            , which assign to each input word a cost in R\n            <jats:sup>\u22650<\/jats:sup>\n            . By relating the \u201cunbounded look ahead\u201d of optimal offline algorithms with nondeterminism, and relating the \u201cno look ahead\u201d of online algorithms with determinism, we are able to solve problems about the competitive ratio of online algorithms, and the memory they require, by reducing them to questions about\n            <jats:italic>determinization<\/jats:italic>\n            and\n            <jats:italic>approximated determinization<\/jats:italic>\n            of weighted automata.\n          <\/jats:p>","DOI":"10.1145\/1721837.1721844","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Reasoning about online algorithms with weighted automata"],"prefix":"10.1145","volume":"6","author":[{"given":"Benjamin","family":"Aminof","sequence":"first","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robby","family":"Lampert","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321632"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ball T. Cook B. Levin V. and Rajamani S. 2004. Slam and static driver verifier: Technology transfer of formal methods inside microsoft. In Integrated Formal Methods. 1--20.  Ball T. Cook B. Levin V. and Rajamani S. 2004. Slam and static driver verifier: Technology transfer of formal methods inside microsoft. In Integrated Formal Methods. 1--20.","DOI":"10.1007\/978-3-540-24756-2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00034-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294260"},{"key":"e_1_2_1_5_1","unstructured":"Borodin A. and El-Yaniv R. 1998. Online Computation and Competitive Analysis. Cambridge University Press.   Borodin A. and El-Yaniv R. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28435"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90017-A"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11560548_7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/007\/02"},{"key":"e_1_2_1_10_1","unstructured":"Clarke E. Grumberg O. and Peled D. 1999. Model Checking. MIT Press.   Clarke E. Grumberg O. and Peled D. 1999. Model Checking. MIT Press."},{"volume":"1427","volume-title":"Proceedings of the 10th International Conference on Computer Aided Verification. Lecture Notes in Computer Science","author":"Elgaard J.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the 17th International Conference on Automated Deduction. 236--255","author":"Emerson E.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","unstructured":"Harrison M. 1965. Introduction to Switching and Automata Theory. McGraw-Hill.  Harrison M. 1965. Introduction to Switching and Automata Theory. McGraw-Hill."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_26"},{"key":"e_1_2_1_15_1","unstructured":"Holzmann G. 2004. The Spin Model Checker:Primer and Reference Manual. Addison-Wesley.   Holzmann G. 2004. The Spin Model Checker:Primer and Reference Manual. Addison-Wesley."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770351.1770390"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1956.11988793"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kuich W. and Salomaa A. 1986. Semirings Automata Languages. EATCS Monographs on Theoretical Computer Science. Springer.   Kuich W. and Salomaa A. 1986. Semirings Automata Languages. EATCS Monographs on Theoretical Computer Science. Springer.","DOI":"10.1007\/978-3-642-69959-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_2_1_20_1","unstructured":"McCluskey E. 1965. Introduction to the Theory of Switching Circuits. McGraw-Hill.  McCluskey E. 1965. Introduction to the Theory of Switching Circuits. McGraw-Hill."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/972695.972698"},{"key":"e_1_2_1_22_1","unstructured":"Rudolph L. 1986. The ski-rental problem. As described in a Hebrew Univeristy lecture.  Rudolph L. 1986. The ski-rental problem. As described in a Hebrew Univeristy lecture."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1092"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721844","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721844","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721844"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721844","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}