{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:48:43Z","timestamp":1725738523181},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392115"},{"type":"electronic","value":"9783642392122"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39212-2_20","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:09:19Z","timestamp":1372770559000},"page":"199-211","source":"Crossref","is-referenced-by-count":3,"title":["Stochastic Context-Free Grammars, Regular Languages, and Newton\u2019s Method"],"prefix":"10.1007","author":[{"given":"Kousha","family":"Etessami","sequence":"first","affiliation":[]},{"given":"Alistair","family":"Stewart","sequence":"additional","affiliation":[]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"9","key":"20_CR1","doi-asserted-by":"publisher","first-page":"936","DOI":"10.1109\/34.93811","volume":"13","author":"A. Corazza","year":"1991","unstructured":"Corazza, A., De Mori, R., Gretter, D., Satta, G.: Computation of probabilities for an island-driven parser. IEEE Trans. PAMI\u00a013(9), 936\u2013950 (1991)","journal-title":"IEEE Trans. PAMI"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids. Cambridge U. Press (1999)","DOI":"10.1017\/CBO9780511790492"},{"key":"20_CR3","unstructured":"Esparza, J., Gaiser, A., Kiefer, S.: Computing least fixed points of probabilistic systems of polynomials. In: Proc. 27th STACS, pp. 359\u2013370 (2010)"},{"issue":"6","key":"20_CR4","doi-asserted-by":"publisher","first-page":"2282","DOI":"10.1137\/090749591","volume":"39","author":"J. Esparza","year":"2010","unstructured":"Esparza, J., Kiefer, S., Luttenberger, M.: Computing the least fixed point of positive polynomial systems. SIAM J. on Computing\u00a039(6), 2282\u20132355 (2010)","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"20_CR5","first-page":"1","volume":"2","author":"J. Esparza","year":"2006","unstructured":"Esparza, J., Ku\u010dera, A., Mayr, R.: Model checking probabilistic pushdown automata. Logical Methods in Computer Science\u00a02(1), 1\u201331 (2006)","journal-title":"Logical Methods in Computer Science"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-642-31594-7_27","volume-title":"Automata, Languages, and Programming","author":"K. Etessami","year":"2012","unstructured":"Etessami, K., Stewart, A., Yannakakis, M.: Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 314\u2013326. Springer, Heidelberg (2012); See full version at ArXiv:1202.4798"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Etessami, K., Stewart, A., Yannakakis, M.: Polynomial-time algorithms for multi-type branching processes and stochastic context-free grammars. In: Proc. 44th ACM STOC, Full version is available at ArXiv:1201.2374 (2012)","DOI":"10.1145\/2213977.2214030"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Etessami, K., Stewart, A., Yannakakis, M.: Stochastic Context-Free Grammars, Regular Languages, and Newton\u2019s method, Full preprint of this paper: ArXiv:1302.6411 (2013)","DOI":"10.1007\/978-3-642-39212-2_20"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Etessami, K., Yannakakis, M.: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM\u00a056(1) (2009)","DOI":"10.1145\/1462153.1462154"},{"issue":"2","key":"20_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2159531.2159534","volume":"13","author":"K. Etessami","year":"2012","unstructured":"Etessami, K., Yannakakis, M.: Model checking of recursive probabilistic systems. ACM Trans. Comput. Log.\u00a013(2), 12 (2012)","journal-title":"ACM Trans. Comput. Log."},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge U. Press (1985)","DOI":"10.1017\/CBO9780511810817"},{"issue":"3","key":"20_CR12","first-page":"315","volume":"17","author":"F. Jelinek","year":"1991","unstructured":"Jelinek, F., Lafferty, J.D.: Computation of the probability of initial substring generation by stochastic context-free grammars. Computational Linguistics\u00a017(3), 315\u2013323 (1991)","journal-title":"Computational Linguistics"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"3423","DOI":"10.1093\/nar\/gkg614","volume":"31","author":"B. Knudsen","year":"2003","unstructured":"Knudsen, B., Hein, J.: Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res\u00a031, 3423\u20133428 (2003)","journal-title":"Nucleic Acids Res"},{"key":"20_CR14","unstructured":"Manning, C., Sch\u00fctze, H.: Foundations of Statistical Natural Language Processing. MIT Press (1999)"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Nederhof, M.-J., Satta, G.: Estimation of consistent probabilistic context-free grammars. In: HLT-NAACL (2006)","DOI":"10.3115\/1220835.1220879"},{"issue":"2","key":"20_CR16","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s11168-008-9052-8","volume":"6","author":"M.-J. Nederhof","year":"2008","unstructured":"Nederhof, M.-J., Satta, G.: Computing partition functions of PCFGs. Research on Language and Computation\u00a06(2), 139\u2013162 (2008)","journal-title":"Research on Language and Computation"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-540-78291-9_7","volume":"113","author":"M.-J. Nederhof","year":"2008","unstructured":"Nederhof, M.-J., Satta, G.: Probabilistic parsing. New Developments in Formal Languages and Applications\u00a0113, 229\u2013258 (2008)","journal-title":"New Developments in Formal Languages and Applications"},{"key":"20_CR18","unstructured":"Nederhof, M.-J., Satta, G.: Computation of infix probabilities for probabilistic context-free grammars. In: EMNLP, pp. 1213\u20131221 (2011)"},{"issue":"9","key":"20_CR19","doi-asserted-by":"publisher","first-page":"1052","DOI":"10.1109\/34.615455","volume":"19","author":"J. S\u00e1nchez","year":"1997","unstructured":"S\u00e1nchez, J., Bened\u00ed, J.-M.: Consistency of stochastic context-free grammars from probabilistic estimation based on growth transformations. IEEE Trans. Pattern Anal. Mach. Intell.\u00a019(9), 1052\u20131055 (1997)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Stewart, A., Etessami, K., Yannakakis, M.: Upper bounds for Newton\u2019s method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata, Arxiv:1302.3741 (2013) (conference version to appear in CAV 2013)","DOI":"10.1007\/978-3-642-39799-8_33"},{"issue":"2","key":"20_CR21","first-page":"167","volume":"21","author":"A. Stolcke","year":"1995","unstructured":"Stolcke, A.: An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics\u00a021(2), 167\u2013201 (1995)","journal-title":"Computational Linguistics"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-540-71209-1_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"D. Wojtczak","year":"2007","unstructured":"Wojtczak, D., Etessami, K.: Premo: an analyzer for probabilistic recursive models. In: Grumberg, O., Huth, M. (eds.) TACAS 2007. LNCS, vol.\u00a04424, pp. 66\u201371. Springer, Heidelberg (2007)"}],"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-39212-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,29]],"date-time":"2020-07-29T14:18:40Z","timestamp":1596032320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39212-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392115","9783642392122"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39212-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}