{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T09:42:56Z","timestamp":1725615776779},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642243714"},{"type":"electronic","value":"9783642243721"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24372-1_16","type":"book-chapter","created":{"date-parts":[[2011,9,29]],"date-time":"2011-09-29T09:41:14Z","timestamp":1317289274000},"page":"213-227","source":"Crossref","is-referenced-by-count":6,"title":["Formal Analysis of Online Algorithms"],"prefix":"10.1007","author":[{"given":"Benjamin","family":"Aminof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robby","family":"Lampert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/PL00009158","volume":"18","author":"S. Albers","year":"1997","unstructured":"Albers, S.: On the influence of lookahead in competitive paging algorithms. Algorithmica\u00a018, 283\u2013305 (1997)","journal-title":"Algorithmica"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Aminof, B., Kupferman, O., Lampert, R.: Reasoning about online algorithms with weighted automata. ACM Transactions on Algorithms\u00a06(2) (2010)","DOI":"10.1145\/1721837.1721844"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Aminof, B., Kupferman, O., Lampert, R.: Rigorous Approximated Determinization of Weighted Automata. In: Proc. 26th LICS, pp. 345\u2013354 (2011)","DOI":"10.1109\/LICS.2011.50"},{"issue":"2-3","key":"16_CR4","first-page":"171","volume":"10","author":"R.I. Bahar","year":"1997","unstructured":"Bahar, R.I., Frohm, E.A., Gaona, C.M., Hachtel, G.D., Macii, E., Pardo, A., Somenzi, F.: Algebraic decision diagrams and their applications. FMSD\u00a010(2-3), 171\u2013206 (1997)","journal-title":"FMSD"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R.M., Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica\u00a011(2), 2\u201314 (1994)","journal-title":"Algorithmica"},{"key":"16_CR6","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge Univ. Press, Cambridge (1998)"},{"issue":"2","key":"16_CR7","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A. Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive Paging with Locality of Reference. J. Comput. Syst. Sci.\u00a050(2), 244\u2013258 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1-2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(98)00118-2","volume":"209","author":"D. Breslauer","year":"1998","unstructured":"Breslauer, D.: On competitive on-line paging with lookahead. TCS\u00a0209(1-2), 365\u2013375 (1998)","journal-title":"TCS"},{"issue":"8","key":"16_CR9","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"C-35","author":"R.E. Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean-function manipulation. IEEE Transactions on Computing\u00a0C-35(8), 677\u2013691 (1986)","journal-title":"IEEE Transactions on Computing"},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0890-5401(92)90017-A","volume":"98","author":"J.R. Burch","year":"1992","unstructured":"Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: 1020 states and beyond. Information and Computation\u00a098(2), 142\u2013170 (1992)","journal-title":"Information and Computation"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/11560548_7","volume-title":"Correct Hardware Design and Verification Methods","author":"A. Chakrabarti","year":"2005","unstructured":"Chakrabarti, A., Chatterjee, K., Henzinger, T.A., Kupferman, O., Majumdar, R.: Verifying quantitative properties using bound functions. In: Borrione, D., Paul, W. (eds.) CHARME 2005. LNCS, vol.\u00a03725, pp. 50\u201364. Springer, Heidelberg (2005)"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-85361-9_14","volume-title":"CONCUR 2008 - Concurrency Theory","author":"K. Chatterjee","year":"2008","unstructured":"Chatterjee, K., Henzinger, T., Jobstmann, B.: Environment assumptions for synthesis. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol.\u00a05201, pp. 147\u2013161. Springer, Heidelberg (2008)"},{"issue":"2","key":"16_CR13","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M. Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New Results on Server Problems. SIAM J. Discrete Math.\u00a04(2), 172\u2013181 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Larmore, L.L.: The server problem and on-line games. In: On-line Algorithms. DIMACS Series DMTCS, vol.\u00a07, pp. 11\u201364 (1992)","DOI":"10.1090\/dimacs\/007\/02"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02124674","volume":"9","author":"F.R.K. Chung","year":"1989","unstructured":"Chung, F.R.K., Graham, R.L., Saks, M.E.: A dynamic location problem for graphs. Combinatorica\u00a09(2), 111\u2013131 (1989)","journal-title":"Combinatorica"},{"key":"16_CR16","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4886-6","volume-title":"Fairness","author":"N. Francez","year":"1986","unstructured":"Francez, N.: Fairness. Texts and Monographs in Computer Science. Springer, Heidelberg (1986)"},{"issue":"2-3","key":"16_CR17","first-page":"149","volume":"10","author":"M. Fujita","year":"1997","unstructured":"Fujita, M., McGeer, P.C., Yang, J.C.-Y.: Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation. FMSD\u00a010(2-3), 149\u2013169 (1997)","journal-title":"FMSD"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Harel, D., Pnueli, A.: On the development of reactive systems. In: Logics and Models of Concurrent Systems. NATO ASI, vol.\u00a0F-13, pp. 477\u2013498 (1985)","DOI":"10.1007\/978-3-642-82453-1_17"},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-642-12032-9_18","volume-title":"Foundations of Software Science and Computational Structures","author":"M. Holtmann","year":"2010","unstructured":"Holtmann, M., Kaiser, \u0141., Thomas, W.: Degrees of lookahead in regular\u00a0infinite\u00a0games. In: Ong, L. (ed.) FOSSACS 2010. LNCS, vol.\u00a06014, pp. 252\u2013266. Springer, Heidelberg (2010)"},{"key":"16_CR20","first-page":"935","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complement. I&C\u00a017, 935\u2013938 (1988)","journal-title":"I&C"},{"issue":"1","key":"16_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S. Irani","year":"1994","unstructured":"Irani, S.: Coloring inductive graphs on-line. Algorithmica\u00a011(1), 53\u201372 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"16_CR22","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0020-0190(91)90231-6","volume":"38","author":"M.-Y. Kao","year":"1991","unstructured":"Kao, M.-Y., Tate, S.R.: Online matching with blocked input. Inf. Process. Lett.\u00a038(3), 113\u2013116 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"16_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A.R. Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica\u00a03(1), 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"16_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69959-7","volume-title":"Semirings, Automata, Languages","author":"W. Kuich","year":"1986","unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata, Languages. Springer, Heidelberg (1986)"},{"issue":"2","key":"16_CR25","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M.S. Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms\u00a011(2), 208\u2013230 (1990)","journal-title":"J. Algorithms"},{"issue":"2","key":"16_CR26","first-page":"269","volume":"23","author":"M. Mohri","year":"1997","unstructured":"Mohri, M.: Finite-state transducers in language and speech processing. Computational Linguistics\u00a023(2), 269\u2013311 (1997)","journal-title":"Computational Linguistics"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Pnueli, A.: In transition from global to modular temporal reasoning about programs. In: Logics and Models of Concurrent Systems. NATO ASI, vol.\u00a0F-13, pp. 123\u2013144 (1985)","DOI":"10.1007\/978-3-642-82453-1_5"},{"issue":"2","key":"16_CR28","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"key":"16_CR29","unstructured":"Somenzi, F.: CUDD package, 2.4.1., \n                    \n                      http:\/\/vlsi.colorado.edu\/~fabio\/CUDD\/"},{"key":"16_CR30","unstructured":"Whaley, J.: JavaBDD package, 1.0b2., \n                    \n                      http:\/\/javabdd.sourceforge.net\/"},{"key":"16_CR31","unstructured":"Young, N.: On-line caching as cache size varies. In: Proc. 2nd SODA, pp. 241\u2013250 (1991)"}],"container-title":["Lecture Notes in Computer Science","Automated Technology for Verification and Analysis"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24372-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T06:49:33Z","timestamp":1554706173000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24372-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642243714","9783642243721"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24372-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}