{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:51:52Z","timestamp":1778298712939,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540656999","type":"print"},{"value":"9783540490999","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49099-x_2","type":"book-chapter","created":{"date-parts":[[2007,6,24]],"date-time":"2007-06-24T21:03:21Z","timestamp":1182719001000},"page":"2-19","source":"Crossref","is-referenced-by-count":34,"title":["A Decidable Logic for Describing Linked Data Structures"],"prefix":"10.1007","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Reps","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mooly","family":"Sagiv","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,28]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"U. Assmann and M. Weinhardt. Interprocedural heap analysis for parallelizing imperative programs. In W. K. Giloi, S. J\u00e4hnichen, and B. D. Shriver, editors, Programming Models For Massively Parallel Computers, pages 74\u201382, Washington, DC, September 1993. IEEE Press.","DOI":"10.1109\/PMMP.1993.315553"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"E. Boerger, E. Graedel, and Y. Gurevich. The Classical Decision Problem. Springer-Verlag, 1996.","DOI":"10.1007\/978-3-642-59207-2_1"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"D.R. Chase, M. Wegman, and F. Zadeck. Analysis of pointers and structures. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 296\u2013310, New York, NY, 1990. ACM Press.","DOI":"10.1145\/93548.93585"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"A. Deutsch. A storeless model for aliasing and its abstractions using finite representations of right-regular equivalence relations. In IEEE International Conference on Computer Languages, pages 2\u201313, Washington, DC, 1992. IEEE Press.","DOI":"10.1109\/ICCL.1992.185463"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"A. Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 230\u2013241, New York, NY, 1994. ACM Press.","DOI":"10.1145\/773473.178263"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Pascal Fradet and Daniel LeMetayer. Shape types. In Symp. on Princ. of Prog. Lang., New York, NY, 1997. ACM Press.","DOI":"10.1145\/263699.263706"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"R Ghiya and L. Hendren. Putting pointer analysis to work. In Symp. on Princ. of Prog. Lang., New York, NY, 1998. ACM Press.","DOI":"10.1145\/268946.268957"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"R. Ghiya and L.J. Hendren. Connection analysis: A practical interprocedural heap analysis for C. In Proc. of the 8th Int. Workshop on Lang. and Comp. for Par. Comp., number 1033 in Lec. Notes in Comp. Sci., pages 515\u2013534, Columbus, Ohio, August 1995. Springer-Verlag.","DOI":"10.1007\/BFb0014221"},{"key":"2_CR9","volume-title":"Parallelizing Programs with Recursive Data Structures","author":"L. Hendren","year":"1990","unstructured":"L. Hendren. Parallelizing Programs with Recursive Data Structures. PhD thesis, Cornell Univ., Ithaca, NY, Jan 1990."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"L. Hendren, J. Hummel, and A. Nicolau. Abstractions for recursive pointer data structures: Improving the analysis and the transformation of imperative programs. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 249\u2013260, New York, NY, June 1992. ACM Press.","DOI":"10.1145\/143103.143138"},{"issue":"1","key":"2_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1109\/71.80123","volume":"1","author":"L. Hendren","year":"1990","unstructured":"L. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. IEEE Trans. on Par. and Dist. Syst., 1(1):35\u201347, January 1990.","journal-title":"IEEE Trans. on Par. and Dist. Syst."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"S. Horwitz, P. Pfeifer, and T. Reps. Dependence analysis for pointer variables. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 28\u201340, New York, NY, 1989. ACM Press.","DOI":"10.1145\/74818.74821"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"J.L. Jensen, M.E. Joergensen, N. UKlarlund, and M.I. Schwartzbach. Automatic verification of pointer programs using monadic second-order logic. In SIGPLAN Conf. on Prog. Lang. Design and Impl., 1997.","DOI":"10.1145\/258915.258936"},{"key":"2_CR14","first-page":"102","volume-title":"Program Flow Analysis: Theory and Applications","author":"N.D. Jones","year":"1981","unstructured":"N.D. Jones and S.S. Muchnick. Flow analysis and optimization of Lisp-like structures. In S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 4, pages 102\u2013131. Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"N.D. Jones and S.S. Muchnick. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In Symp. on Princ. of Prog. Lang, pages 66\u201374, New York, NY, 1982. ACM Press.","DOI":"10.1145\/582153.582161"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"N. Klarlund and M. Schwartzbach. Graph types. In Symp. on Princ. of Prog. Lang., New York, NY, January 1993. ACM Press.","DOI":"10.1145\/158511.158628"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"J.R. Larus and P.N. Hilfnger. Detecting conflicts between structure accesses. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 21\u201334, New York, NY, 1988. ACM Press.","DOI":"10.1145\/53990.53993"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"C.-K. Luk and T.C. Mowry. Compiler-based prefetching for recursive data structures. In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, pages 222\u2013233, October 1996.","DOI":"10.1145\/237090.237190"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"J. Plevyak, A.A. Chien, and V. Karamcheti. Analysis of dynamic structures for efficient parallel execution. In U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Languages and Compilers for Parallel Computing, volume 768 of Lec. Notes in Comp. Sci., pages 37\u201357, Portland, OR, August 1993. Springer-Verlag.","DOI":"10.1007\/3-540-57659-2_3"},{"key":"2_CR20","series-title":"Tech. Rep. TR-1383, Comp. Sci. Dept.","volume-title":"Parametric shape analysis via 3-valued logic","author":"M. Sagiv","year":"1998","unstructured":"M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. Tech. Rep. TR-1383, Comp. Sci. Dept. Univ. of Wisconsin, Madison, WI, July 1998. Available at \u201c http:\/\/www.cs.wisc.edu\/wpis\/papers\/parametric.ps \u201d."},{"issue":"1","key":"2_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/271510.271517","volume":"20","author":"M. Sagiv","year":"1998","unstructured":"M. Sagiv, T. Reps, and R. Wilhelm. Solving shape-analysis problems in languages with destructive updating. Trans. on Prog. Lang. and Syst., 20(1):1\u201350, January 1998.","journal-title":"Trans. on Prog. Lang. and Syst."},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. In Symp. on Princ. of Prog. Lang., 1999. Available at \u201c http:\/\/www.cs.wisc.edu\/wpis\/papers\/popl99.ps \u201d.","DOI":"10.1145\/292540.292552"},{"issue":"1","key":"2_CR23","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/0890-5401(92)90076-R","volume":"101","author":"J. Stransky","year":"1992","unstructured":"J. Stransky. A lattice for abstract interpretation of dynamic (Lisp-like) structures. Inf. and Comp., 101(1):70\u2013102, Nov. 1992.","journal-title":"Inf. and Comp."},{"issue":"3","key":"2_CR24","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1145\/322261.322273","volume":"28","author":"R.E. Tarjan","year":"1981","unstructured":"R.E. Tarjan. Fast algorithms for solving path problems. J. ACM, 28(3):594\u2013614,1981.","journal-title":"J. ACM"},{"issue":"3","key":"2_CR25","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1145\/322261.322272","volume":"28","author":"R.E. Tarjan","year":"1981","unstructured":"R.E. Tarjan. A unified approach to path problems. J. ACM, 28(3):577\u2013593, 1981.","journal-title":"J. ACM"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"J.W. Thatcher and J.B. Wright. Generalized finite automata with an application to a decision problem of second order logic. Math. Syst. Theory, 2:57\u201382, 1968.","journal-title":"Math. Syst. Theory"},{"key":"2_CR27","volume-title":"Analysis of Recursive Types in an Imperative Language","author":"E. Y.-B. Wang","year":"1994","unstructured":"E. Y.-B. Wang. Analysis of Recursive Types in an Imperative Language. PhD thesis, Univ. of Calif., Berkeley, CA, 1994."}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49099-X_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T13:56:22Z","timestamp":1737122182000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49099-X_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656999","9783540490999"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-49099-x_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}