{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:38:22Z","timestamp":1725521902742},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540418627"},{"type":"electronic","value":"9783540453093"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45309-1_13","type":"book-chapter","created":{"date-parts":[[2008,11,28]],"date-time":"2008-11-28T00:39:26Z","timestamp":1227832766000},"page":"190-205","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Constant Propagation"],"prefix":"10.1007","author":[{"given":"Markus","family":"M\u00fcller-Olm","sequence":"first","affiliation":[]},{"given":"Oliver","family":"R\u00fcthing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,3,23]]},"reference":[{"key":"13_CR1","unstructured":"A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, 1985."},{"issue":"2","key":"13_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1145\/201059.201061","volume":"17","author":"C. Click","year":"1995","unstructured":"C. Click and K. D. Cooper. Combining analyses, combining optimizations. ACM Transactions on Programming Languages and Systems, 17(2):181\u2013196, 1995.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"13_CR3","volume-title":"Computers and Intractability-A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability-A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, San Francisco, 1979."},{"key":"13_CR4","volume-title":"Flow Analysis of Computer Programs","author":"M. S. Hecht","year":"1977","unstructured":"M. S. Hecht. Flow Analysis of Computer Programs. Elsevier, North-Holland, 1977."},{"key":"13_CR5","unstructured":"N. D. Jones and S. S Muchnick. Complexity of flow analysis, inductive assertion synthesis, and a language due to Dijkstra. In [10], chapter 12, pages 380\u2013393."},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF00268497","volume":"6","author":"M. Karr","year":"1976","unstructured":"M. Karr. Affine relationships among variables of a program. Acta Informatica, 6:133\u2013151, 1976.","journal-title":"Acta Informatica"},{"key":"13_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-46423-9_7","volume-title":"CC\u2019 2000","author":"J. Knoop","year":"2000","unstructured":"J. Knoop and O. R\u00fcthing. Constant propagation on the value graph: simple constants and beyond. In CC\u2019 2000, LNCS 1781, pages 94\u2013109, Berlin, Germany, 2000. Springer-Verlag."},{"issue":"4","key":"13_CR8","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/161494.161501","volume":"1","author":"W. Landi","year":"1992","unstructured":"W. Landi. Undecidability of static analysis. ACM Letters on Programming Languages and Systems, 1(4):323\u2013337, 1992.","journal-title":"ACM Letters on Programming Languages and Systems"},{"key":"13_CR9","volume-title":"Advanced Compiler Design & Implementation","author":"S. S. Muchnick","year":"1997","unstructured":"S. S. Muchnick. Advanced Compiler Design & Implementation. Morgan Kaufmann, San Francisco, CA, 1997."},{"volume-title":"Program Flow Analysis: Theory and Applications","year":"1981","key":"13_CR10","unstructured":"S. S. Muchnick and N. D. Jones, editors. Program Flow Analysis: Theory and Applications. Prentice Hall, Englewood Cliffs, NJ, 1981."},{"key":"13_CR11","series-title":"Lect Notes Comput Sci","volume-title":"STACS\u20192001","author":"M. M\u00fcller-Olm","year":"2001","unstructured":"M. M\u00fcller-Olm. The complexity of copy constant detection in parallel programs. In STACS\u20192001, LNCS, 2001. Springer-Verlag. To appear."},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/325694.325704","volume-title":"POPL\u20192000","author":"R. Muth","year":"2000","unstructured":"R. Muth and S. Debray. On the complexity of flow-sensitive dataflow analysis. In POPL\u20192000, pages 67\u201381, ACM, Boston, MA, 2000."},{"key":"13_CR13","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"W. Pugh. The Omega Test: a fast and practical integer programming algorithm for dependence analysis. In IEEE, editor, Supercomputing\u2019 91, Albuquerque, NM, pages 4\u201313. IEEE Computer Society Press, 1991.","DOI":"10.1145\/125826.125848"},{"issue":"3","key":"13_CR15","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1145\/291889.291900","volume":"20","author":"W. Pugh","year":"1998","unstructured":"W. Pugh and D. Wonnacott. Constraint-based array dependence analysis. ACM Transactions on Programming Languages and Systems, 20(3):635\u2013678, 1998.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"13_CR16","first-page":"104","volume-title":"POPL\u201977","author":"J. H. Reif","year":"1977","unstructured":"J. H. Reif and R. Lewis. Symbolic evaluation and the gobal value graph. POPL\u201977, pages 104\u2013118, ACM, Los Angeles, CA, 1977."},{"issue":"1-2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(96)00072-2","volume":"167","author":"M. Sagiv","year":"1996","unstructured":"M. Sagiv, T. Reps, and S. Horwitz. Precise interprocedural dataflow analysis with applications to constant propagation. Theoretical Computer Science, 167(1-2):131\u2013170, 1996.","journal-title":"Theoretical Computer Science"},{"key":"13_CR18","unstructured":"M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In [10], chapter 7, pages 189\u2013233."},{"issue":"2","key":"13_CR19","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(91)90392-F","volume":"80","author":"B. Steffen","year":"1991","unstructured":"B. Steffen and J. Knoop. Finite constants: Characterizations of a new decidable set of constants. Theoretical Computer Science, 80(2):303\u2013318, 1991.","journal-title":"Theoretical Computer Science"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2), 1991.","DOI":"10.1145\/103135.103136"}],"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-45309-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T17:08:06Z","timestamp":1684688886000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45309-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540418627","9783540453093"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45309-1_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}