{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:07:13Z","timestamp":1767236833985,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214030","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"579-588","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars"],"prefix":"10.1145","author":[{"given":"Kousha","family":"Etessami","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Alistair","family":"Stewart","sequence":"additional","affiliation":[{"name":"School of Informatics, University of Edinburgh, United Kingdom"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.3115\/1034678.1034759"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_3_2_2_3_1","volume-title":"Mathematical Analysis","author":"Apostol T.","year":"1974","unstructured":"T. Apostol . Mathematical Analysis . Addison-Wesley , 2 nd edition, 1974 . T. Apostol. Mathematical Analysis. Addison-Wesley, 2nd edition, 1974.","edition":"2"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.19"},{"key":"e_1_3_2_2_5_1","volume-title":"Geometric Programming","author":"Duffin R. J.","year":"1967","unstructured":"R. J. Duffin , E. L. Peterson , and C. Zener . Geometric Programming . John Wiley and Sons , 1967 . R. J. Duffin, E. L. Peterson, and C. Zener. Geometric Programming. John Wiley and Sons, 1967."},{"key":"e_1_3_2_2_6_1","volume-title":"Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids","author":"Durbin R.","year":"1999","unstructured":"R. Durbin , S. R. Eddy , A. Krogh , and G. Mitchison . Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids . Cambridge U. Press , 1999 . R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids. Cambridge U. Press, 1999."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.3115\/1034678.1034759"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_3_2_2_9_1","volume-title":"Mathematical Analysis","author":"Apostol T.","year":"1974","unstructured":"T. Apostol . Mathematical Analysis . Addison-Wesley , 2 nd edition, 1974 . T. Apostol. Mathematical Analysis. Addison-Wesley, 2nd edition, 1974.","edition":"2"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.19"},{"key":"e_1_3_2_2_11_1","volume-title":"Geometric Programming","author":"Duffin R. J.","year":"1967","unstructured":"R. J. Duffin , E. L. Peterson , and C. Zener . Geometric Programming . John Wiley and Sons , 1967 . R. J. Duffin, E. L. Peterson, and C. Zener. Geometric Programming. John Wiley and Sons, 1967."},{"key":"e_1_3_2_2_12_1","volume-title":"Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids","author":"Durbin R.","year":"1999","unstructured":"R. Durbin , S. R. Eddy , A. Krogh , and G. Mitchison . Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids . Cambridge U. Press , 1999 . R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids. Cambridge U. Press, 1999."},{"key":"e_1_3_2_2_13_1","first-page":"359","volume-title":"Proc. 27th STACS","author":"Esparza J.","year":"2010","unstructured":"J. Esparza , A. Gaiser , and S. Kiefer . Computing least fixed points of probabilistic systems of polynomials . In Proc. 27th STACS , pages 359 -- 370 , 2010 . J. Esparza, A. Gaiser, and S. Kiefer. Computing least fixed points of probabilistic systems of polynomials. In Proc. 27th STACS, pages 359--370, 2010."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/090749591"},{"issue":"1","key":"e_1_3_2_2_15_1","first-page":"1","article-title":"Model checking probabilistic pushdown automata","volume":"2","author":"Esparza J.","year":"2006","unstructured":"J. Esparza , A. Kucera , and R. Mayr . Model checking probabilistic pushdown automata . Logical Methods in Computer Science , 2 ( 1 ): 1 -- 31 , 2006 . J. Esparza, A. Kucera, and R. Mayr. Model checking probabilistic pushdown automata. Logical Methods in Computer Science, 2(1):1 -- 31, 2006.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_2_16_1","volume-title":"Polynomial-time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. ArXiv:1202.4798","author":"Etessami K.","year":"2012","unstructured":"K. Etessami , A. Stewart , and M. Yannakakis . Polynomial-time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. ArXiv:1202.4798 , 2012 . K. Etessami, A. Stewart, and M. Yannakakis. Polynomial-time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. ArXiv:1202.4798, 2012."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214030"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2009.12.009"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159531.2159534"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335362"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629136"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-51866-9"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/b97371"},{"key":"e_1_3_2_2_26_1","first-page":"783","article-title":"The calculation of final probabilities for branching random processes","volume":"56","author":"Kolmogorov A. N.","year":"1947","unstructured":"A. N. Kolmogorov and B. A. Sevastyanov . The calculation of final probabilities for branching random processes . Doklady , 56 : 783 -- 786 , 1947 . (Russian). A. N. Kolmogorov and B. A. Sevastyanov. The calculation of final probabilities for branching random processes. Doklady, 56:783--786, 1947. (Russian).","journal-title":"Doklady"},{"key":"e_1_3_2_2_27_1","volume-title":"Foundations of Statistical Natural Language Processing","author":"Manning C.","year":"1999","unstructured":"C. Manning and H. Sch\u00fctze . Foundations of Statistical Natural Language Processing . MIT Press , 1999 . C. Manning and H. Sch\u00fctze. Foundations of Statistical Natural Language Processing. MIT Press, 1999."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-009-9062-1"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78291-9_7"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763507.1763517"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York USA","acronym":"STOC'12"},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214030","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214030","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214030"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":30,"alternative-id":["10.1145\/2213977.2214030","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214030","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}