{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T11:08:25Z","timestamp":1772104105330,"version":"3.50.1"},"reference-count":25,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2007,7,5]],"date-time":"2007-07-05T00:00:00Z","timestamp":1183593600000},"content-version":"vor","delay-in-days":5695,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"National Science Foundation","award":["NCR-9016211"],"award-info":[{"award-number":["NCR-9016211"]}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["88-0189."],"award-info":[{"award-number":["88-0189."]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1991,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We analyze the performance of a prototypical scheme for shared storage allocation: two initially empty stacks evolving in a contiguous block of memory of size <jats:italic>m.<\/jats:italic> We treat the case in which the stacks are more likely to shrink than grow, but with the probabilities of insertion and deletion allowed to depend arbitrarily on stack height as a fraction of <jats:italic>m.<\/jats:italic> New results are obtained on the <jats:italic>m<\/jats:italic> \u2192 \u221e asymptotics of the stack collision time, and of the final stack heights. The results of Wentzell and Freidlin on the large deviations of Markov chains are used, and the relation of their formalism to the Hamiltonian formulation of classical mechanics is emphasized. Certain results on higher\u2010order asymptotics follow from WKB expansions.<\/jats:p>","DOI":"10.1002\/rsa.3240020404","type":"journal-article","created":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T05:55:38Z","timestamp":1278914138000},"page":"379-420","source":"Crossref","is-referenced-by-count":24,"title":["Colliding stacks: A large deviations analysis"],"prefix":"10.1002","volume":"2","author":[{"given":"Robert S.","family":"Maier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,7,5]]},"reference":[{"key":"e_1_2_1_1_2","unstructured":"N. I.Akhiezer The Calculus of Variations Blaisdell 1962."},{"key":"e_1_2_1_2_2","volume-title":"Large Deviation Techniques in Decision, Simulation and Estimation","author":"Bucklew J. A.","year":"1990"},{"key":"e_1_2_1_3_2","first-page":"805","volume-title":"The Whys of Subnuclear Physics: Proceedings of the 1977 International School, Erice, Italy","author":"Coleman S.","year":"1977"},{"key":"e_1_2_1_4_2","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","year":"1966"},{"key":"e_1_2_1_5_2","first-page":"325","volume-title":"Mathematical Foundations of Computer Science: Proceedings of the 12th Symposium, Bratislava, Czechoslovakia","author":"Flajolet P.","year":"1986"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21967"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-0176-9"},{"key":"e_1_2_1_8_2","volume-title":"Classical Mechanics","author":"Goldstein H.","year":"1980"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90061-6"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90211-F"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0145059"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0145062"},{"key":"e_1_2_1_13_2","volume-title":"Fundamental Algorithms","author":"Knuth D. E.","year":"1981"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90028-4"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52590-4_52"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176992161"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"R. S.Maier A path integral approach to dynamic data structures J. Complexity (Sept.1991).","DOI":"10.1016\/0885-064X(91)90035-V"},{"key":"e_1_2_1_18_2","volume-title":"Matrix\u2010Geometric Solutions in Stochastic Models","author":"Neuts M.","year":"1981"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(80)80020-X"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/321607.321617"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.2914703"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970241"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1121030"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/1121062"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210029"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240020404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240020404","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240020404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T06:15:32Z","timestamp":1698041732000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240020404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,12]]}},"alternative-id":["10.1002\/rsa.3240020404"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240020404","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}