{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:37:02Z","timestamp":1775054222028,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642005893","type":"print"},{"value":"9783642005909","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-00590-9_13","type":"book-chapter","created":{"date-parts":[[2009,3,27]],"date-time":"2009-03-27T08:05:58Z","timestamp":1238141158000},"page":"175-189","source":"Crossref","is-referenced-by-count":14,"title":["An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees"],"prefix":"10.1007","author":[{"given":"Hao","family":"Yuan","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Eugster","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"11-12","key":"13_CR1","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0950-5849(98)00093-7","volume":"40","author":"T.W. Reps","year":"1998","unstructured":"Reps, T.W.: Program analysis via graph reachability. Information & Software Technology\u00a040(11-12), 701\u2013726 (1998)","journal-title":"Information & Software Technology"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Rehof, J., F\u00e4hndrich, M.: Type-based flow analysis: From polymorphic subtyping to CFL-reachability. In: Proceedings of the 28th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2001), pp. 54\u201366 (2001)","DOI":"10.1145\/373243.360208"},{"key":"13_CR3","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 (2005)","DOI":"10.1145\/1094811.1094817"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Sridharan, M., Bod\u00edk, R.: Refinement-based context-sensitive points-to analysis for Java. In: Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation (PLDI 2006), pp. 387\u2013400 (2006)","DOI":"10.1145\/1133981.1134027"},{"key":"13_CR5","volume-title":"The art of computer programming, volume III: sorting and searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The art of computer programming, volume III: sorting and searching. Addison-Wesley, Reading (1973)"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1287\/opre.12.3.450","volume":"12","author":"S. Hakimi","year":"1964","unstructured":"Hakimi, S.: Optimum locations of switching center and the absolute center and medians of a graph. Operations Research\u00a012, 450\u2013459 (1964)","journal-title":"Operations Research"},{"key":"13_CR7","volume-title":"The art of computer programming, volume I: fundamental algorithms","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The art of computer programming, volume I: fundamental algorithms. Addison-Wesley, Reading (1973)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1990), pp. 230\u2013242 (1990)","DOI":"10.1145\/298514.298576"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Reps, T.W., Horwitz, S., Sagiv, S.: Precise interprocedural dataflow analysis via graph reachability. In: Conference Record of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1995), pp. 49\u201361 (1995)","DOI":"10.1145\/199448.199462"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Reps, T.W.: Shape analysis as a generalized path problem. In: Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 1995), pp. 1\u201311 (1995)","DOI":"10.1145\/215465.215466"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Zheng, X., Rugina, R.: Demand-driven alias analysis for C. In: Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2008), pp. 197\u2013208 (2008)","DOI":"10.1145\/1328438.1328464"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: Subcubic algorithms for recursive state machines. In: Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2008), pp. 159\u2013169 (2008)","DOI":"10.1145\/1328438.1328460"},{"key":"13_CR13","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronok, M.A., Faradzev, I.A.: On economical construction of the transitive closure of an oriented graph. Soviet Mathematics Doklady\u00a011, 1209\u20131210 (1970)","journal-title":"Soviet Mathematics Doklady"},{"issue":"3","key":"13_CR14","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(83)90063-7","volume":"16","author":"W. Rytter","year":"1983","unstructured":"Rytter, W.: Time complexity of loop-free two-way pushdown automata. Inf. Process. Lett.\u00a016(3), 127\u2013129 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"1-3","key":"13_CR15","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/S0019-9958(85)80024-3","volume":"67","author":"W. Rytter","year":"1986","unstructured":"Rytter, W.: Fast recognition of pushdown automaton and context-free languages. Inf. Control\u00a067(1-3), 12\u201322 (1986)","journal-title":"Inf. Control"},{"issue":"4","key":"13_CR16","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1145\/1075382.1075387","volume":"27","author":"R. Alur","year":"2005","unstructured":"Alur, R., Benedikt, M., Etessami, K., Godefroid, P., Reps, T.W., Yannakakis, M.: Analysis of recursive state machines. ACM Transactions on Programming Languags and Systems\u00a027(4), 786\u2013818 (2005)","journal-title":"ACM Transactions on Programming Languags and Systems"},{"key":"13_CR17","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 (2004)","DOI":"10.1145\/996841.996867"},{"key":"13_CR18","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)"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1145\/1265530.1265564","volume-title":"PODS 2007: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems","author":"R. Alur","year":"2007","unstructured":"Alur, R.: Marrying words and trees. In: PODS 2007: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 233\u2013242. ACM, New York (2007)"},{"issue":"2","key":"13_CR20","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":"13_CR21","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1287\/trsc.5.2.212","volume":"5","author":"A. Goldman","year":"1971","unstructured":"Goldman, A.: Optimal center location in a simple network. Transportation Science\u00a05, 212\u2013221 (1971)","journal-title":"Transportation Science"},{"issue":"2","key":"13_CR22","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal of Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal of Computing"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics, pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00590-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T00:23:44Z","timestamp":1558225424000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00590-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642005893","9783642005909"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00590-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}