{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T12:56:13Z","timestamp":1769000173939,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642182747","type":"print"},{"value":"9783642182754","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-18275-4_21","type":"book-chapter","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T00:06:38Z","timestamp":1295222798000},"page":"294-308","source":"Crossref","is-referenced-by-count":4,"title":["String Analysis as an Abstract Interpretation"],"prefix":"10.1007","author":[{"given":"Se-Won","family":"Kim","sequence":"first","affiliation":[]},{"given":"Kwang-Moo","family":"Choe","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/1007352.1007390","volume-title":"STOC 2004: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing","author":"R. Alur","year":"2004","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: STOC 2004: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 202\u2013211. ACM, New York (2004)"},{"issue":"3","key":"21_CR2","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1145\/177492.177768","volume":"16","author":"J. Bates","year":"1994","unstructured":"Bates, J., Lavie, A.: Recognizing substrings of LR(k) languages in linear time. ACM Trans. Program. Lang. Syst.\u00a016(3), 1051\u20131077 (1994)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.3115\/981623.981641","volume-title":"Proceedings of the 27th Annual Meeting on Association for Computational Linguistics","author":"S. Billot","year":"1989","unstructured":"Billot, S., Lang, B.: The structure of shared forests in ambiguous parsing. In: Proceedings of the 27th Annual Meeting on Association for Computational Linguistics, pp. 143\u2013151. Association for Computational Linguistics, Morristown (1989)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Choi, T.-H., Lee, O., Kim, H., Doh, K.-G.: A practical string analyzer by the widening approach. In: APLAS, pp. 374\u2013388 (2006)","DOI":"10.1007\/11924661_23"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44898-5_1","volume-title":"Static Analysis","author":"A.S. Christensen","year":"2003","unstructured":"Christensen, A.S., M\u00f8ller, A., Schwartzbach, M.I.: Precise analysis of string expressions. In: Cousot, R. (ed.) SAS 2003. LNCS, vol.\u00a02694, pp. 1\u201318. Springer, Heidelberg (2003), http:\/\/www.brics.dk\/JSA\/"},{"issue":"4","key":"21_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1093\/logcom\/2.4.511","volume":"2","author":"P. Cousot","year":"1992","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation frameworks. Journal of Logic and Computation\u00a02(4), 511\u2013547 (1992)","journal-title":"Journal of Logic and Computation"},{"key":"21_CR7","first-page":"238","volume-title":"POPL 1977: Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages","author":"P. Cousot","year":"1977","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL 1977: Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 238\u2013252. ACM, New York (1977)"},{"key":"21_CR8","first-page":"269","volume-title":"POPL 1979: Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages","author":"P. Cousot","year":"1979","unstructured":"Cousot, P., Cousot, R.: Systematic design of program analysis frameworks. In: POPL 1979: Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 269\u2013282. ACM, New York (1979)"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-03237-0_18","volume-title":"Static Analysis","author":"K.-G. Doh","year":"2009","unstructured":"Doh, K.-G., Kim, H., Schmidt, D.A.: Abstract parsing: Static analysis of dynamically generated string output using LR-parsing technology. In: Palsberg, J., Su, Z. (eds.) SAS 2009. LNCS, vol.\u00a05673, pp. 256\u2013272. Springer, Heidelberg (2009)"},{"issue":"4","key":"21_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(76)90074-8","volume":"1","author":"E.P. Friedman","year":"1976","unstructured":"Friedman, E.P.: The inclusion problem for simple languages. Theor. Comput. Sci.\u00a01(4), 297\u2013316 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"21_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0304-3975(00)00296-6","volume":"267","author":"H. Goeman","year":"2001","unstructured":"Goeman, H.: On parsing and condensing substrings of LR languages in linear time. Theor. Comput. Sci.\u00a0267(1-2), 61\u201382 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"21_CR12","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1145\/322217.322224","volume":"27","author":"S.A. Greibach","year":"1980","unstructured":"Greibach, S.A., Friedman, E.P.: Superdeterministic pdas: A subcase with a decidable inclusion problem. J. ACM\u00a027(4), 675\u2013700 (1980)","journal-title":"J. ACM"},{"issue":"1","key":"21_CR13","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"S.A. Greibach","year":"1965","unstructured":"Greibach, S.A.: A new normal-form theorem for context-free phrase structure grammars. J. ACM\u00a012(1), 42\u201352 (1965)","journal-title":"J. ACM"},{"key":"21_CR14","unstructured":"Kim, S.-W.: Proofs for formalizing string analysis within abstract interpretation framework. Technical report, KAIST (2010), http:\/\/pllab.kaist.ac.kr\/~sewon.kim\/papers\/pf-saai-tr.pdf"},{"key":"21_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/11823230_22","volume-title":"Static Analysis","author":"C. Kirkegaard","year":"2006","unstructured":"Kirkegaard, C., M\u00f8ller, A.: Static analysis for java servlets and JSP. In: Yi, K. (ed.) SAS 2006. LNCS, vol.\u00a04134, pp. 336\u2013352. Springer, Heidelberg (2006)"},{"issue":"3","key":"21_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0019-9958(67)90564-5","volume":"11","author":"D.E. Knuth","year":"1967","unstructured":"Knuth, D.E.: A characterization of parenthesis languages. Information and Control\u00a011(3), 269\u2013289 (1967)","journal-title":"Information and Control"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1145\/1621607.1621625","volume-title":"GPCE 2009: Proceedings of the Eighth International Conference on Generative Programming and Component Engineering","author":"S. Kong","year":"2009","unstructured":"Kong, S., Choi, W., Yi, K.: Abstract parsing for two-staged languages with concatenation. In: GPCE 2009: Proceedings of the Eighth International Conference on Generative Programming and Component Engineering, pp. 109\u2013116. ACM, New York (2009)"},{"key":"21_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/3-540-06841-4_65","volume-title":"Automata, Languages and Programming","author":"B. Lang","year":"1974","unstructured":"Lang, B.: Deterministic techniques for efficient non-deterministic parsers. In: Loeckx, J. (ed.) ICALP 1974. LNCS, vol.\u00a014, pp. 255\u2013269. Springer, Heidelberg (1974)"},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.3115\/991635.991710","volume-title":"Proceedings of the 12th conference on Computational linguistics","author":"B. Lang","year":"1988","unstructured":"Lang, B.: Parsing incomplete sentences. In: Proceedings of the 12th conference on Computational linguistics, pp. 365\u2013371. ACL, Morristown (1988)"},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-540-31987-0_2","volume-title":"Programming Languages and Systems","author":"L. Mauborgne","year":"2005","unstructured":"Mauborgne, L., Rival, X.: Trace partitioning in abstract interpretation based static analyzers. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol.\u00a03444, pp. 5\u201320. Springer, Heidelberg (2005)"},{"key":"21_CR21","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1145\/1060745.1060809","volume-title":"WWW 2005: Proceedings of the 14th International Conference on World Wide Web","author":"Y. Minamide","year":"2005","unstructured":"Minamide, Y.: Static approximation of dynamically generated web pages. In: WWW 2005: Proceedings of the 14th International Conference on World Wide Web, pp. 432\u2013441. ACM, New York (2005)"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Minamide, Y., Tozawa, A.: Xml validation for context-free grammars. In: APLAS, pp. 357\u2013373 (2006)","DOI":"10.1007\/11924661_22"},{"issue":"3","key":"21_CR23","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1145\/233551.233555","volume":"43","author":"M.-J. Nederhof","year":"1996","unstructured":"Nederhof, M.-J., Bertsch, E.: Linear-time suffix parsing for deterministic languages. J. ACM\u00a043(3), 524\u2013554 (1996)","journal-title":"J. ACM"},{"key":"21_CR24","unstructured":"Vall\u00e9e-Rai, R., Hendren, L., Sundaresan, V., Lam, P., Gagnon, E., Co, P.: Soot - a java optimization framework. In: Proceedings of CASCON 1999, pp. 125\u2013135 (1999)"},{"issue":"5","key":"21_CR25","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/122501.122505","volume":"26","author":"J. Rekers","year":"1991","unstructured":"Rekers, J., Koorn, W.: Substring parsing for arbitrary context-free grammars. SIGPLAN Not.\u00a026(5), 59\u201366 (1991)","journal-title":"SIGPLAN Not."},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/1040294.1040300","volume-title":"TLDI 2005: Proceedings of the 2005 ACM SIGPLAN International Workshop on Types in Languages Design and Implementation","author":"P. Thiemann","year":"2005","unstructured":"Thiemann, P.: Grammar-based analysis of string expressions. In: TLDI 2005: Proceedings of the 2005 ACM SIGPLAN International Workshop on Types in Languages Design and Implementation, pp. 59\u201370. ACM, New York (2005)"}],"container-title":["Lecture Notes in Computer Science","Verification, Model Checking, and Abstract Interpretation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18275-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T09:14:22Z","timestamp":1637140462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18275-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642182747","9783642182754"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18275-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}