{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T02:27:23Z","timestamp":1784255243904,"version":"3.55.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319663340","type":"print"},{"value":"9783319663357","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-66335-7_1","type":"book-chapter","created":{"date-parts":[[2017,8,10]],"date-time":"2017-08-10T03:53:48Z","timestamp":1502337228000},"page":"3-19","source":"Crossref","is-referenced-by-count":3,"title":["Extending Parikh\u2019s Theorem to Weighted and Probabilistic Context-Free Grammars"],"prefix":"10.1007","author":[{"given":"Vijay","family":"Bhattiprolu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Spencer","family":"Gordon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,11]]},"reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/1721837.1721844","volume":"6","author":"B Aminof","year":"2010","unstructured":"Aminof, B., Kupferman, O., Lampert, R.: Reasoning about online algorithms with weighted automata. ACM Trans. Algorithms 6(2), 28 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/3-540-49257-7_19","volume-title":"Database Theory \u2014 ICDT\u201999","author":"C Beeri","year":"1999","unstructured":"Beeri, C., Milo, T.: Schemas for integration and translation of structured and semi-structured data. In: Beeri, C., Buneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 296\u2013313. Springer, Heidelberg (1999). doi: 10.1007\/3-540-49257-7_19"},{"key":"1_CR3","unstructured":"Bhattiprolu, V., Gordon, S., Viswanathan, M.: Extending Parikh\u2019s theorem to weighted and probabilistic context-free grammars. Technical report, University of Illinois, Urbana-Champaign (2017). http:\/\/hdl.handle.net\/2142\/96262"},{"issue":"5","key":"1_CR4","doi-asserted-by":"crossref","first-page":"1502","DOI":"10.1137\/S0097539798346676","volume":"30","author":"A Buchsbaum","year":"2000","unstructured":"Buchsbaum, A., Giancarlo, R., Westbrook, J.: On the determinization of weighted finite automata. SIAM J. Comput. 30(5), 1502\u20131531 (2000)","journal-title":"SIAM J. Comput."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-87531-4_28","volume-title":"Computer Science Logic","author":"K Chatterjee","year":"2008","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Quantitative languages. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol. 5213, pp. 385\u2013400. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-87531-4_28"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-03409-1_2","volume-title":"Fundamentals of Computation Theory","author":"K Chatterjee","year":"2009","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Alternating weighted automata. In: Kuty\u0142owski, M., Charatonik, W., G\u0119bala, M. (eds.) FCT 2009. LNCS, vol. 5699, pp. 3\u201313. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-03409-1_2"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0097-8493(93)90079-O","volume":"17","author":"K Culik","year":"1993","unstructured":"Culik, K., Kari, J.: Image compression using weighted finite automata. Comput. Graph. 17, 305\u2013313 (1993)","journal-title":"Comput. Graph."},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/10722167_9","volume-title":"Computer Aided Verification","author":"Z Dang","year":"2000","unstructured":"Dang, Z., Ibarra, O.H., Bultan, T., Kemmerer, R.A., Su, J.: Binary reachability analysis of discrete pushdown timed automata. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 69\u201384. Springer, Heidelberg (2000). doi: 10.1007\/10722167_9"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/11523468_42","volume-title":"Automata, Languages and Programming","author":"M Droste","year":"2005","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 513\u2013525. Springer, Heidelberg (2005). doi: 10.1007\/11523468_42"},{"key":"1_CR10","volume-title":"Handbook of Weighted Automata","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. Springer, Heidelberg (2009)"},{"issue":"1","key":"1_CR11","doi-asserted-by":"crossref","first-page":"13","DOI":"10.3233\/FI-1997-3112","volume":"31","author":"J Esparza","year":"1997","unstructured":"Esparza, J.: Petri nets, commutative context-free grammars, and basic parallel processes. Fundam. Inform. 31(1), 13\u201325 (1997)","journal-title":"Fundam. Inform."},{"issue":"12","key":"1_CR12","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1016\/j.ipl.2011.03.019","volume":"111","author":"J Esparza","year":"2011","unstructured":"Esparza, J., Ganty, P., Kiefer, S., Luttenberger, M.: Parikh\u2019s theorem: a simple and direct automaton construction. Inf. Process. Lett. 111(12), 614\u2013619 (2011)","journal-title":"Inf. Process. Lett."},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(77)90103-0","volume":"19","author":"J Goldstine","year":"1977","unstructured":"Goldstine, J.: A simplified proof of Parikh\u2019s theorem. Discret. Math. 19, 235\u2013239 (1977)","journal-title":"Discret. Math."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"G\u00f6ller, S., Mayr, R., To, A.: On the computational complexity of verifying one-counter processes. In: Proceedings of the IEEE Symposium on Logic in Computer Science, pp. 235\u2013244 (2009)","DOI":"10.1109\/LICS.2009.37"},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(81)90028-3","volume":"22","author":"E Gurari","year":"1981","unstructured":"Gurari, E., Ibarra, O.: The complexity of decision problems for finite-turn multi-counter machines. J. Comput. Syst. Sci. 22, 220\u2013229 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR16","unstructured":"Hafner, U.: Low bit-rate image and video coding with weighted finite automata. Ph.D. thesis, Universit\u00e4t W\u00fcrzburg (1999)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/3-540-10003-2_81","volume-title":"Automata, Languages and Programming","author":"T-D Huynh","year":"1980","unstructured":"Huynh, T.-D.: The complexity of semilinear sets. In: Bakker, J., Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 324\u2013337. Springer, Heidelberg (1980). doi: 10.1007\/3-540-10003-2_81"},{"key":"1_CR18","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(84)90092-6","volume":"33","author":"D Huynh","year":"1984","unstructured":"Huynh, D.: Deciding the ineuivalence of context-free grammars with 1-letter terminal alphabet is $$\\sigma ^p_2$$ \u03c3 2 p -complete. Theor. Comput. Sci. 33, 305\u2013326 (1984)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1_CR19","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0019-9958(85)80015-2","volume":"66","author":"D Huynh","year":"1985","unstructured":"Huynh, D.: Complexity of equivalence problems for commutative grammars. Inf. Control 66(1), 103\u2013121 (1985)","journal-title":"Inf. Control"},{"key":"1_CR20","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O Ibarra","year":"1978","unstructured":"Ibarra, O.: Reversal-bounded multi-counter machines and their decision problems. J. ACM 25, 116\u2013133 (1978)","journal-title":"J. ACM"},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/3-540-44968-X_44","volume-title":"Computing and Combinatorics","author":"Z Jiang","year":"2000","unstructured":"Jiang, Z., Litow, B., Vel, O.: Similarity enrichment in image compression through weighted finite automata. In: Du, D.-Z.-Z., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds.) COCOON 2000. LNCS, vol. 1858, pp. 447\u2013456. Springer, Heidelberg (2000). doi: 10.1007\/3-540-44968-X_44"},{"key":"1_CR22","unstructured":"Katritzke, F.: Refinements of data compression using weighted finite automata. Ph.D. thesis, Universit\u00e4t Siegen (2001)"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Kopczy\u0144ski, E., To, A.: Parikh images of grammars: complexity and applications. In: Proceedings of the IEEE Symposium on Logic in Computer Science, pp. 80\u201389 (2010)","DOI":"10.1109\/LICS.2010.21"},{"key":"1_CR24","unstructured":"Kuperberg, D.: Linear temporal logic for regular cost functions. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science, pp. 627\u2013636 (2011)"},{"key":"1_CR25","first-page":"269","volume":"23","author":"M Mohri","year":"1997","unstructured":"Mohri, M.: Finite-state transducers in language and speech processing. Comput. Linguist. 23, 269\u2013311 (1997)","journal-title":"Comput. Linguist."},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(99)00014-6","volume":"231","author":"M Mohri","year":"1997","unstructured":"Mohri, M., Pereira, F., Riley, M.: The design principles of weighted finite-state transducer library. Theor. Comput. Sci. 231, 17\u201332 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1_CR27","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"RJ Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"1_CR28","volume-title":"Introduction to Probabilistic Automata","author":"A Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, Cambridge (1971)"},{"issue":"3","key":"1_CR29","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M Rabin","year":"1963","unstructured":"Rabin, M.: Probabilistic automata. Inf. Control 6(3), 230\u2013245 (1963)","journal-title":"Inf. Control"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-540-77050-3_4","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"T Reps","year":"2007","unstructured":"Reps, T., Lal, A., Kidd, N.: Program analysis using weighted pushdown systems. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 23\u201351. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-77050-3_4"},{"issue":"1\u20132","key":"1_CR31","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.scico.2005.02.009","volume":"58","author":"T Reps","year":"2005","unstructured":"Reps, T., Schwoon, S., Jha, S., Melski, D.: Weighted pushdown systems and their application to interprocedural dataflow analysis. Sci. Comput. Program. 58(1\u20132), 206\u2013263 (2005)","journal-title":"Sci. Comput. Program."},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.: On the definition of a family of automata. Inf. Control 4, 245\u2013270 (1961)","journal-title":"Inf. Control"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/11817963_29","volume-title":"Computer Aided Verification","author":"K Sen","year":"2006","unstructured":"Sen, K., Viswanathan, M.: Model checking multithreaded programs with asynchronous atomic methods. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 300\u2013314. Springer, Heidelberg (2006). doi: 10.1007\/11817963_29"},{"key":"1_CR34","first-page":"575","volume":"2","author":"H Siedl","year":"2007","unstructured":"Siedl, H., Schwentick, T., Muscholl, A.: Counting in trees. Texts Log. Games 2, 575\u2013612 (2007)","journal-title":"Texts Log. Games"},{"key":"1_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-642-12032-9_16","volume-title":"Foundations of Software Science and Computational Structures","author":"AW To","year":"2010","unstructured":"To, A.W., Libkin, L.: Algorithmic metatheorems for decidable LTL model checking over infinite systems. In: Ong, L. (ed.) FoSSaCS 2010. LNCS, vol. 6014, pp. 221\u2013236. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-12032-9_16"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Wich, K.: Exponential ambiguity of context-free grammars. In: Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6\u20139 July 1999, pp. 125\u2013138 (1999)","DOI":"10.1142\/9789812792464_0011"},{"key":"1_CR37","first-page":"301","volume":"179","author":"H Yen","year":"1996","unstructured":"Yen, H.: On reachability equivalence for BPP-nets. Theor. Comput. Sci. 179, 301\u2013317 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Quantitative Evaluation of Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66335-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T21:38:01Z","timestamp":1750801081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66335-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319663340","9783319663357"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66335-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}