{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T21:01:08Z","timestamp":1751662868120,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662466629"},{"type":"electronic","value":"9783662466636"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46663-6_10","type":"book-chapter","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T18:37:47Z","timestamp":1427913467000},"page":"193-211","source":"Crossref","is-referenced-by-count":1,"title":["Towards a Scalable Framework for Context-Free Language Reachability"],"prefix":"10.1007","author":[{"given":"Nicholas","family":"Hollingum","sequence":"first","affiliation":[]},{"given":"Bernhard","family":"Scholz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/3-540-51084-2_9","volume-title":"Symbolic and Algebraic Computation","author":"S.K. Abdali","year":"1989","unstructured":"Abdali, S.K., Wise, D.S.: Experiments with quadtree representation of matrices. In: Gianni, P. (ed.) ISSAC 1988. LNCS, vol.\u00a0358, pp. 96\u2013108. Springer, Heidelberg (1989)"},{"key":"10_CR2","volume-title":"Foundations of Databases: The Logical Level","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V. (eds.): Foundations of Databases: The Logical Level, 1st edn. Addison-Wesley Longman Publishing Co., Inc., MA (1995)","edition":"1"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Bastani, O., Anand, S., Aiken, A.: Specification inference using context-free language reachability. In: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 553\u2013566. ACM (2015)","DOI":"10.1145\/2775051.2676977"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bravenboer, M., Smaragdakis, Y.: Strictly declarative specification of sophisticated points-to analyses. In: Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA 2009, pp. 243\u2013262. ACM, New York (2009)","DOI":"10.1145\/1640089.1640108"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: Subcubic algorithms for recursive state machines. In: Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, pp. 159\u2013169. ACM, New York (2008)","DOI":"10.1145\/1328438.1328460"},{"key":"10_CR6","unstructured":"Cocke, J.: Programming languages and their compilers. Courant Institute Math. Sci., New York, USA (1970)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09(3), 251\u2013280 (1990); Computational algebraic complexity editorial","DOI":"10.1016\/S0747-7171(08)80013-2"},{"issue":"1-3","key":"10_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0019-9958(82)90401-6","volume":"55","author":"D. Dolev","year":"1982","unstructured":"Dolev, D., Even, S., Karp, R.M.: On the security of ping-pong protocols. Information and Control\u00a055(1-3), 57\u201368 (1982)","journal-title":"Information and Control"},{"issue":"3","key":"10_CR9","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1145\/355791.355796","volume":"4","author":"F.G. Gustavson","year":"1978","unstructured":"Gustavson, F.G.: Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Trans. Math. Softw.\u00a04(3), 250\u2013269 (1978)","journal-title":"ACM Trans. Math. Softw."},{"issue":"6","key":"10_CR10","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1145\/1273442.1250767","volume":"42","author":"B. Hardekopf","year":"2007","unstructured":"Hardekopf, B., Lin, C.: The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code. SIGPLAN Not.\u00a042(6), 290\u2013299 (2007)","journal-title":"SIGPLAN Not."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Heintze, N., McAllester, D.: On the cubic bottleneck in subtyping and flow analysis. In: Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, LICS 1997, pp. 342\u2013351. IEEE (1997)","DOI":"10.1109\/LICS.1997.614960"},{"key":"10_CR12","unstructured":"Hollingum, N.: Source code for worklist and semi-naive cfl-r algorithms (October 2014), http:\/\/sydney.edu.au\/engineering\/it\/~nhol8058\/cfl\/"},{"key":"10_CR13","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, International edn. Pearson Education International Inc., Upper Saddle River (2003)"},{"key":"10_CR14","unstructured":"Kasami, T.: An efficient recognition and syntax-analysis algorithm for context-free languages. Technical report, DTIC Document (1965)"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Kodumal, J., Aiken, A.: The set constraint\/cfl reachability connection in practice. In: Proceedings of the ACM SIGPLAN, Conference on Programming Language Design and Implementation, PLDI 2004, pp. 207\u2013218. ACM, New York (2004)","DOI":"10.1145\/996841.996867"},{"key":"10_CR16","first-page":"2008","volume":"8","author":"M. Lange","year":"2009","unstructured":"Lange, M., Lei\u00df, H.: To cnf or not to cnf? an efficient yet presentable version of the cyk algorithm. Informatica Didactica\u00a08, 2008\u20132010 (2009)","journal-title":"Informatica Didactica"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-37051-9_4","volume-title":"Compiler Construction","author":"Y. Lu","year":"2013","unstructured":"Lu, Y., Shang, L., Xie, X., Xue, J.: An incremental points-to analysis with cfl-reachability. In: Jhala, R., De Bosschere, K. (eds.) Compiler Construction. LNCS, vol.\u00a07791, pp. 61\u201381. Springer, Heidelberg (2013)"},{"issue":"1\u20132","key":"10_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0304-3975(00)00049-9","volume":"248","author":"D. Melski","year":"2000","unstructured":"Melski, D., Reps, T.: Interconvertibility of a class of set constraints and context-free-language reachability. Theoretical Computer Science\u00a0248(1\u20132), 29\u201398 (2000)","journal-title":"Theoretical Computer Science"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Mendez-Lojo, M., Burtscher, M., Pingali, K.: A gpu implementation of inclusion-based points-to analysis. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2012, pp. 107\u2013116. ACM, New York (2012)","DOI":"10.1145\/2145816.2145831"},{"key":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-642-14455-4_31","volume-title":"Developments in Language Theory","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Fast parsing for boolean grammars: A generalization of valiants algorithm. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol.\u00a06224, pp. 340\u2013351. Springer, Heidelberg (2010)"},{"issue":"5","key":"10_CR21","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/BF03036473","volume":"33","author":"T. Reps","year":"1996","unstructured":"Reps, T.: On the sequential nature of interprocedural program-analysis problems. Acta Informatica\u00a033(5), 739\u2013757 (1996)","journal-title":"Acta Informatica"},{"issue":"11-12","key":"10_CR22","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0950-5849(98)00093-7","volume":"40","author":"T. Reps","year":"1998","unstructured":"Reps, T.: Program analysis via graph reachability. Information and Software Technology\u00a040(11-12), 701\u2013726 (1998)","journal-title":"Information and Software Technology"},{"key":"10_CR23","first-page":"49","volume-title":"Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1995","author":"T. Reps","year":"1995","unstructured":"Reps, T., Horwitz, S., Sagiv, M.: Precise interprocedural dataflow analysis via graph reachability. In: Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1995, pp. 49\u201361. ACM, New York (1995)"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Sagiv, M., Reps, T., Horwitz, S.: Precise interprocedural dataflow analysis with applications to constant propagation. In: Mosses, P.D., Nielsen, M., Schwartzbach, M. (eds.) TAPSOFT 1995. LNCS, vol.\u00a0915, pp. 651\u2013665. Springer, Heidelberg (1995)","DOI":"10.1007\/3-540-59293-8_226"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Sridharan, M., Gopan, D., Shan, L., Bod\u00edk, R.: Demand-driven points-to analysis for java. In: Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA 2005, pp. 59\u201376. ACM, New York (2005)","DOI":"10.1145\/1094811.1094817"},{"issue":"2","key":"10_CR26","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. Journal of Computer and System Sciences\u00a010(2), 308\u2013315 (1975)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/978-3-642-11957-6_30","volume-title":"Programming Languages and Systems","author":"D. Vardoulakis","year":"2010","unstructured":"Vardoulakis, D., Shivers, O.: Cfa2: A context-free approach to control-flow analysis. In: Gordon, A.D. (ed.) ESOP 2010. LNCS, vol.\u00a06012, pp. 570\u2013589. Springer, Heidelberg (2010)"},{"key":"10_CR28","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/2001420.2001440","volume-title":"Proceedings of the 2011 International Symposium on Software Testing and Analysis, ISSTA 2011","author":"D. Yan","year":"2011","unstructured":"Yan, D., Xu, G., Rountev, A.: Demand-driven context-sensitive alias analysis for java. In: Proceedings of the 2011 International Symposium on Software Testing and Analysis, ISSTA 2011, pp. 155\u2013165. ACM, New York (2011)"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1145\/298514.298576","volume-title":"Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1990","author":"M. Yannakakis","year":"1990","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1990, pp. 230\u2013242. ACM, New York (1990)"},{"issue":"2","key":"10_CR30","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D.H. Younger","year":"1967","unstructured":"Younger, D.H.: Recognition and parsing of context-free languages in time n 3. Information and control\u00a010(2), 189\u2013208 (1967)","journal-title":"Information and control"},{"key":"10_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-642-00590-9_13","volume-title":"Programming Languages and Systems","author":"H. Yuan","year":"2009","unstructured":"Yuan, H., Eugster, P.: An efficient algorithm for solving the dyck-cfl reachability problem on trees. In: Castagna, G. (ed.) ESOP 2009. LNCS, vol.\u00a05502, pp. 175\u2013189. Springer, Heidelberg (2009)"},{"issue":"1","key":"10_CR32","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Trans. Algorithms\u00a01(1), 2\u201313 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/2491956.2462159","volume-title":"Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013","author":"Q. Zhang","year":"2013","unstructured":"Zhang, Q., Lyu, M.R., Yuan, H., Su, Z.: Fast algorithms for dyck-cfl-reachability with applications to alias analysis. In: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013, pp. 435\u2013446. ACM, New York (2013)"},{"key":"10_CR34","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1145\/2660193.2660213","volume-title":"Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2014","author":"Q. Zhang","year":"2014","unstructured":"Zhang, Q., Xiao, X., Zhang, C., Yuan, H., Su, Z.: Efficient subcubic alias analysis for c. In: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2014, pp. 829\u2013845. ACM, New York (2014)"},{"issue":"1","key":"10_CR35","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1145\/1328897.1328464","volume":"43","author":"X. Zheng","year":"2008","unstructured":"Zheng, X., Rugina, R.: Demand-driven alias analysis for c. SIGPLAN Not.\u00a043(1), 197\u2013208 (2008)","journal-title":"SIGPLAN Not."}],"container-title":["Lecture Notes in Computer Science","Compiler Construction"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46663-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T20:23:59Z","timestamp":1747859039000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46663-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662466629","9783662466636"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46663-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}