{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:33Z","timestamp":1725558933940},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141614"},{"type":"electronic","value":"9783642141621"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14162-1_45","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:21Z","timestamp":1278321981000},"page":"539-550","source":"Crossref","is-referenced-by-count":2,"title":["Space-Efficient Scheduling of Stochastically Generated Tasks"],"prefix":"10.1007","author":[{"given":"Tom\u00e1\u0161","family":"Br\u00e1zdil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Kiefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Luttenberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, K., Leiserson, C.E., He, Y., Hsu, W.J.: Adaptive work-stealing with parallelism feedback. ACM TOCS\u00a026(3) (2008)","DOI":"10.1145\/1394441.1394443"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240011004","volume":"34","author":"N.S. Arora","year":"2001","unstructured":"Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed microprocessors. Theory of Computing Systems\u00a034, 115\u2013144 (2001)","journal-title":"Theory of Computing Systems"},{"key":"45_CR3","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1214\/aop\/1176991770","volume":"16","author":"K.B. Athreya","year":"1988","unstructured":"Athreya, K.B.: On the maximum sequence of a critical branching process. Annals of Probability\u00a016, 502\u2013507 (1988)","journal-title":"Annals of Probability"},{"key":"45_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-65371-1","volume-title":"Branching Processes","author":"K.B. Athreya","year":"1972","unstructured":"Athreya, K.B., Ney, P.E.: Branching Processes. Springer, Heidelberg (1972)"},{"key":"45_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Heidelberg (1998)"},{"issue":"5","key":"45_CR6","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"R.D. Blumofe","year":"1999","unstructured":"Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. Journal of the ACM\u00a046(5), 720\u2013748 (1999)","journal-title":"Journal of the ACM"},{"issue":"3","key":"45_CR7","doi-asserted-by":"publisher","first-page":"614","DOI":"10.2307\/3215343","volume":"33","author":"K.A. Borovkov","year":"1996","unstructured":"Borovkov, K.A., Vatutin, V.A.: On distribution tails and expectations of maxima in critical branching processes. Journal of Applied Probability\u00a033(3), 614\u2013622 (1996)","journal-title":"Journal of Applied Probability"},{"key":"45_CR8","unstructured":"Br\u00e1zdil, T., Esparza, J., Kiefer, S.: On the memory consumption of probabilistic pushdown automata. In: Proceedings of FSTTCS, pp. 49\u201360 (2009)"},{"key":"45_CR9","unstructured":"Br\u00e1zdil, T., Esparza, J., Kiefer, S., Luttenberger, M.: Space-efficient scheduling of stochastically generated tasks. Technical report (2010), http:\/\/arxiv.org\/abs\/1004.4286"},{"key":"45_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-540-73208-2_17","volume-title":"Developments in Language Theory","author":"J. Esparza","year":"2007","unstructured":"Esparza, J., Kiefer, S., Luttenberger, M.: An extension of Newton\u2019s method to \u03c9-continuous semirings. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 157\u2013168. Springer, Heidelberg (2007)"},{"key":"45_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/978-3-540-70918-3_26","volume-title":"STACS 2007","author":"J. Esparza","year":"2007","unstructured":"Esparza, J., Kiefer, S., Luttenberger, M.: On fixed point equations over commutative semirings. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 296\u2013307. Springer, Heidelberg (2007)"},{"key":"45_CR12","doi-asserted-by":"crossref","unstructured":"Esparza, J., Kiefer, S., Luttenberger, M.: Convergence thresholds of Newton\u2019s method for monotone polynomial equations. In: STACS 2008, pp. 289\u2013300 (2008)","DOI":"10.1145\/1250790.1250822"},{"key":"45_CR13","first-page":"117","volume-title":"LICS 2005","author":"J. Esparza","year":"2005","unstructured":"Esparza, J., Ku\u010dera, A., Mayr, R.: Quantitative analysis of probabilistic pushdown automata: Expectations and variances. In: LICS 2005, pp. 117\u2013126. IEEE, Los Alamitos (2005)"},{"key":"45_CR14","first-page":"12","volume-title":"LICS 2004","author":"J. Esparza","year":"2004","unstructured":"Esparza, J., Ku\u010dera, A., Mayr, R.: Model checking probabilistic pushdown automata. In: LICS 2004, pp. 12\u201321. IEEE Computer Society Press, Los Alamitos (2004)"},{"issue":"1","key":"45_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1462153.1462154","volume":"56","author":"K. Etessami","year":"2009","unstructured":"Etessami, K., Yannakakis, M.: Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM\u00a056(1), 1\u201366 (2009)","journal-title":"Journal of the ACM"},{"key":"45_CR16","volume-title":"An introduction to probability theory and its applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An introduction to probability theory and its applications, vol.\u00a0I. John Wiley & Sons, Chichester (1968)"},{"key":"45_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-51866-9","volume-title":"The Theory of Branching Processes","author":"T.E. Harris","year":"1963","unstructured":"Harris, T.E.: The Theory of Branching Processes. Springer, Heidelberg (1963)"},{"issue":"3","key":"45_CR18","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1145\/174130.174145","volume":"40","author":"R.M. Karp","year":"1993","unstructured":"Karp, R.M., Zhang, Y.: Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM\u00a040(3), 765\u2013789 (1993)","journal-title":"Journal of the ACM"},{"key":"45_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1145\/1250790.1250822","volume-title":"STOC 2007","author":"S. Kiefer","year":"2007","unstructured":"Kiefer, S., Luttenberger, M., Esparza, J.: On the convergence of Newton\u2019s method for monotone systems of polynomial equations. In: STOC 2007, pp. 217\u2013226. ACM, New York (2007)"},{"key":"45_CR20","first-page":"209","volume":"3","author":"T. Lindvall","year":"1976","unstructured":"Lindvall, T.: On the maximum of a branching process. Scandinavian Journal of Statistics\u00a03, 209\u2013214 (1976)","journal-title":"Scandinavian Journal of Statistics"},{"issue":"1","key":"45_CR21","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1145\/314602.314607","volume":"21","author":"G.J. Narlikar","year":"1999","unstructured":"Narlikar, G.J., Belloch, G.E.: Space-efficient scheduling of nested parallelism. ACM TOPLAS\u00a021(1), 138\u2013173 (1999)","journal-title":"ACM TOPLAS"},{"issue":"3","key":"45_CR22","first-page":"131","volume":"4","author":"O. Nerman","year":"1977","unstructured":"Nerman, O.: On the maximal generation size of a non-critical galton-watson process. Scandinavian Journal of Statistics\u00a04(3), 131\u2013135 (1977)","journal-title":"Scandinavian Journal of Statistics"},{"key":"45_CR23","volume-title":"Iterative solution of nonlinear equations in several variables","author":"J.M. Ortega","year":"1970","unstructured":"Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. Academic Press, London (1970)"},{"key":"45_CR24","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1239\/aap\/1035228127","volume":"30","author":"A.G. Pakes","year":"1998","unstructured":"Pakes, A.G.: A limit theorem for the maxima of the para-critical simple branching process. Advances in Applied Probability\u00a030, 740\u2013756 (1998)","journal-title":"Advances in Applied Probability"},{"key":"45_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6257-9","volume-title":"Principles of Random Walk","author":"F. Spitzer","year":"1976","unstructured":"Spitzer, F.: Principles of Random Walk. Springer, Heidelberg (1976)"},{"issue":"4","key":"45_CR26","doi-asserted-by":"publisher","first-page":"893","DOI":"10.2307\/3214692","volume":"28","author":"A. Sp\u0103taru","year":"1991","unstructured":"Sp\u0103taru, A.: A maximum sequence in a critical multitype branching process. Journal of Applied Probability\u00a028(4), 893\u2013897 (1991)","journal-title":"Journal of Applied Probability"},{"key":"45_CR27","volume-title":"Probability with Martingales","author":"D. Williams","year":"1995","unstructured":"Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1995)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14162-1_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T22:38:43Z","timestamp":1685659123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14162-1_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141614","9783642141621"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14162-1_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}