{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:59Z","timestamp":1725664979678},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540606307"},{"type":"electronic","value":"9783540485094"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60630-0_13","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T20:49:59Z","timestamp":1330289399000},"page":"264-289","source":"Crossref","is-referenced-by-count":4,"title":["Parallelism for free: Bitvector analyses \u21d2 no state explosion!"],"prefix":"10.1007","author":[{"given":"Jens","family":"Knoop","sequence":"first","affiliation":[]},{"given":"Bernhard","family":"Steffen","sequence":"additional","affiliation":[]},{"given":"J\u00fcrgen","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Cousot, P., and Cousot, R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the 4\n                th\n                International Symposium on Principles of Programming Languages (POPL'77), Los Angeles, California, 1977, 238\u2013252.","DOI":"10.1145\/512950.512973"},{"key":"13_CR2","unstructured":"Cousot, P., and Cousot, R. Invariance proof methods and analysis techniques for parallel programs. In Biermann, A. W., Guiho, G., and Kodratoff, Y. (eds.) Automatic Program Construction Techniques, chapter 12, 243\u2013271, Macmillan Publishing Company, 1984."},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Chow, J.-H., and Harrison, W. L. Compile time analysis of parallel programs that share memory. In Conference Record of the 19\n                th\n                International Symposium on Principles of Programming Languages (POPL'92), Albuquerque, New Mexico, 1992, 130\u2013141.","DOI":"10.1145\/143165.143194"},{"key":"13_CR4","unstructured":"Chow, J.-H., and Harrison, W. L. State Space Reduction in Abstract Interpretation of Parallel Programs. In Proceedings of the International Conference on Computer Languages, (ICCL'94), Toulouse, France, May 16\u201319, 1994, 277\u2013288."},{"issue":"3","key":"13_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/174146.154197","volume":"18","author":"S. Duri","year":"1993","unstructured":"Duri, S., Buy, U., Devarapalli, R., and Shatz, S. M. Using state space methods for deadlock analysis in Acta tasking. In Proceedings of the ACM SIGSOFT'93 International Symposium on Software Testing and Analysis, Software Engineering Notes 18, 3 (1993), 51\u201360.","journal-title":"Proceedings of the ACM SIGSOFT'93 International Symposium on Software Testing and Analysis, Software Engineering Notes"},{"issue":"5","key":"13_CR6","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1145\/195274.195295","volume":"19","author":"M. B. Dwyer","year":"1994","unstructured":"Dwyer, M. B., and Clarke, L. A. Data flow analysis for verifying properties of concurrent programs. In Proceedings of the 2\n                nd\n                ACM SIG-SOFT'94 Symposium on Foundations of Software Engineering (SIG-SOFT'94), New Orleans, Lousiana, Software Engineering Notes 19, 5 (1994), 62\u201375.","journal-title":"Software Engineering Notes"},{"issue":"7","key":"13_CR7","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1145\/143103.143135","volume":"27","author":"D. M. Dhamdhere","year":"1992","unstructured":"Dhamdhere, D. M., Rosen, B. K., and Zadeck, F. K. How to analyze large programs efficiently and informatively. In Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation (PLDI'92), San Francisco, California, SIGPLAN Notices 27, 7 (1992), 212\u2013223.","journal-title":"SIGPLAN Notices"},{"issue":"5","key":"13_CR8","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/152819.152823","volume":"28","author":"K.-H. Drechsler","year":"1993","unstructured":"Drechsler, K.-H., and Stadel, M. P. A variation of Knoop, R\u00fcthing and Steffen's LAZY CODE MOTION. SIGPLAN Notices 28, 5 (1993), 29\u201338.","journal-title":"SIGPLAN Notices"},{"key":"13_CR9","first-page":"7","volume":"28","author":"D. Grunwald","year":"1993","unstructured":"Grunwald, D., and Srinivasan, H. Data flow equations for explicitely parallel programs. In Proceedings of the ACM SIGPLAN Symposium on Principles of Parallel Programming (PPOPP'93), SIGPLAN Notices 28, 7 (1993).","journal-title":"Proceedings of the ACM SIGPLAN Symposium on Principles of Parallel Programming (PPOPP'93), SIGPLAN Notices"},{"key":"13_CR10","first-page":"332","volume-title":"LNCS 575","author":"P. Godefroid","year":"1991","unstructured":"Godefroid, P., and Wolper, P. Using partial orders for the efficient verification of deadlock freedom and safety properties. In Proceedings of the 3\n                rd\n                International Workshop on Computer Aided Verification (CAV'91), Aalborg, Denmark, Springer-Verlag, LNCS 575 (1991), 332\u2013342."},{"key":"13_CR11","volume-title":"Flow analysis of computer programs","author":"M. S. Hecht","year":"1977","unstructured":"Hecht, M. S. Flow analysis of computer programs. Elsevier, North-Holland, 1977."},{"key":"13_CR12","volume-title":"Introduction to automata theory, languages, and computation","author":"J. E. Hopcroft","year":"1979","unstructured":"Hopcroft, J. E., and Ullman, J. E. Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, Massach., 1979."},{"key":"13_CR13","series-title":"Technical Report No. 72-06-02","volume-title":"Ph.D. dissertation","author":"G. A. Kildall","year":"1972","unstructured":"Kildall, G. A. Global expression optimization during compilation. Ph.D. dissertation, Technical Report No. 72-06-02, University of Washington, Computer Science Group, Seattle, Washington, 1972."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Kildall, G. A. A unified approach to global program optimization. In Conference Record of the 1\n                st\n                ACM Symposium on Principles of Programming Languages (POPL'73), Boston, Massachusetts, 1973, 194\u2013206.","DOI":"10.1145\/512927.512945"},{"issue":"7","key":"13_CR15","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/143103.143136","volume":"27","author":"J. Knoop","year":"1992","unstructured":"Knoop, J., R\u00fcthing, O., and Steffen, B. Lazy code motion. In Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation (PLDI'92), San Francisco, California, SIGPLAN Notices 27, 7 (1992), 224\u2013234.","journal-title":"SIGPLAN Notices"},{"issue":"4","key":"13_CR16","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1145\/183432.183443","volume":"16","author":"J. Knoop","year":"1994","unstructured":"Knoop, J., R\u00fcthing, O., and Steffen, B. Optimal code motion: Theory and practice. Transactions on Programming Languages and Systems 16, 4 (1994), 1117\u20131155.","journal-title":"Transactions on Programming Languages and Systems"},{"issue":"6","key":"13_CR17","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/773473.178256","volume":"29","author":"J. Knoop","year":"1994","unstructured":"Knoop, J., R\u00fcthing, O., and Steffen, B. Partial dead code elimination. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation (PLDI'94), Orlando, Florida, SIGPLAN Notices 29, 6 (1994), 147\u2013158.","journal-title":"SIGPLAN Notices"},{"issue":"6","key":"13_CR18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1145\/223428.207150","volume":"30","author":"J. Knoop","year":"1995","unstructured":"Knoop, J., R\u00fcthing, O., and Steffen, B. The power of assignment motion. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation (PLDI'95), La Jolla, California, SIGPLAN Notices 30, 6 (1995), 233\u2013245.","journal-title":"SIGPLAN Notices"},{"issue":"1","key":"13_CR19","first-page":"71","volume":"1","author":"J. Knoop","year":"1993","unstructured":"Knoop, J., R\u00fcthing, O., and Steffen, B. Lazy strength reduction. Journal of Programming Languages 1, 1 (1993), 71\u201391.","journal-title":"Journal of Programming Languages"},{"key":"13_CR20","first-page":"125","volume-title":"LNCS 641","author":"J. Knoop","year":"1992","unstructured":"Knoop, J., and Steifen, B. The interprocedural coincidence theorem. In Proceedings of the 4\n                th\n                International Conference on Compiler Construction (CC'92), Paderborn, Germany, Springer-Verlag, LNCS 641 (1992), 125\u2013140."},{"key":"13_CR21","first-page":"319","volume":"NS-95-2","author":"J. Knoop","year":"1995","unstructured":"Knoop, J., Steffen, B., and Vollmer, J. Parallelism for free: Efficient and optimal bitvector analyses for parallel programs. In Preliminary Proceedings of the 1\n                st\n                International Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'95), Aarhus, Denmark, BRICS Notes Series NS-95-2 (1995), 319\u2013333.","journal-title":"BRICS Notes Series"},{"key":"13_CR22","volume-title":"MIP-Bericht 9511","author":"J. Knoop","year":"1995","unstructured":"Knoop, J., Steffen, B., and Vollmer, J. Optimal code motion for parallel programs. Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t Passau, Germany, MIP-Bericht 9511 (1995), 30 pages."},{"key":"13_CR23","first-page":"309","volume":"7","author":"J. B. Kam","year":"1977","unstructured":"Kam, J. B., and Ullman, J. D. Monotone data flow analysis frameworks. Acta Informatica 7, (1977), 309\u2013317.","journal-title":"Acta Informatica"},{"key":"13_CR24","first-page":"21","volume":"16","author":"D. Long","year":"1991","unstructured":"Long, D., and Clarke, L. A. Data flow analysis of concurrent systems that use the rendezvous model of synchronization. In Proceedings of the ACM SIGSOFT'91 Symposium on Testing, Analysis, and Verification (TAV4), Victoria, British Columbia, Software Engineering Notes 16, (1991), 21\u201335.","journal-title":"Software Engineering Notes"},{"key":"13_CR25","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF01178576","volume":"30","author":"K. Marriot","year":"1993","unstructured":"Marriot, K. Frameworks for abstract interpretation. Acta Informatica 30, (1993), 103\u2013129.","journal-title":"Acta Informatica"},{"issue":"3","key":"13_CR26","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1016\/0743-7315(89)90004-X","volume":"6","author":"C. E. McDowell","year":"1989","unstructured":"McDowell, C. E. A practical algorithm for static analysis of parallel programs. Journal of Parallel and Distributed Computing 6, 3 (1989), 513\u2013536.","journal-title":"Journal of Parallel and Distributed Computing"},{"volume-title":"Program flow analysis: Theory and applications","year":"1981","key":"13_CR27","unstructured":"Muchnick, S. S., and Jones, N. D. (Eds.). Program flow analysis: Theory and applications. Prentice Hall, Englewood Cliffs, New Jersey, 1981."},{"key":"13_CR28","first-page":"105","volume":"II","author":"S. P. Midkiff","year":"1990","unstructured":"Midkiff, S. P., and Padua, D. A. Issues in the optimization of parallel programs. In Proceedings of the International Conference on Parallel Processing, Volume II, St. Charles, Illinois, (1990), 105\u2013113.","journal-title":"Proceedings of the International Conference on Parallel Processing"},{"key":"13_CR29","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0167-6423(93)90003-8","volume":"21","author":"B. Steffen","year":"1993","unstructured":"Steffen, B. Generating data flow analysis algorithms from modal specifications. Science of Computer Programming 21, (1993), 115\u2013139.","journal-title":"Science of Computer Programming"},{"key":"13_CR30","first-page":"72","volume-title":"LNCS 962","author":"B. Steffen","year":"1995","unstructured":"Steffen, B., Cla\u00dfen, A., Klein, M., Knoop, J., and Margaria, T. The fixpoint-analysis machine. In Proceedings of the 6\n                th\n                International Conference on Concurrency Theory (CONCUR'95), Philadelphia, Pennsylvania, Springer-Verlag, LNCS 962 (1995), 72\u201387."},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Srinivasan, H., Hook, J., and Wolfe, M. Static single assignment form for explicitly parallel programs. In Conference Record of the 20\n                th\n                ACM SIGPLAN Symposium on Principles of Programming Languages (POPL'93), Charleston, South Carolina, 1993, 260\u2013272.","DOI":"10.1145\/158511.158644"},{"key":"13_CR32","first-page":"189","volume-title":"Two approaches to interprocedural data flow analysis","author":"M. Sharir","year":"1981","unstructured":"Sharir, M., and Pnueli, A. Two approaches to interprocedural data flow analysis. In [MJ], 1981, 189\u2013233."},{"key":"13_CR33","first-page":"405","volume-title":"LNCS 589","author":"H. Srinivasan","year":"1991","unstructured":"Srinivasan, H., and Wolfe, M. Analyzing programs with explicit parallelism. In Proceedings of the 4\n                th\n                International Conference on Languages and Compilers for Parallel Computing, Santa Clara, California, Springer-Verlag, LNCS 589 (1991), 405\u2013419."},{"key":"13_CR34","first-page":"156","volume-title":"LNCS 531","author":"A. Valmari","year":"1990","unstructured":"Valmari, A. A stubborn attack on state explosion. In Proceedings of the 2\n                nd\n                International Conference on Computer Aided Verification, New-Brunswick, New Jersey, Springer-Verlag, LNCS 531 (1990), 156\u2013165."},{"key":"13_CR35","volume-title":"Tech. Rep. 2.11.1 of the ESPRIT Project COMPARE #5933","author":"J. Vollmer","year":"1994","unstructured":"Vollmer, J. Data flow equations for parallel programs that share memory. Tech. Rep. 2.11.1 of the ESPRIT Project COMPARE #5933, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, Germany, (1994)."},{"key":"13_CR36","unstructured":"Vollmer, J. Data flow analysis of parallel programs. In Proceedings of the IFIP WG 10.3 Working Conference on Parallel Architectures and Compilation Techniques (PACT'95), Limassol, Cyprus, 1995, 168\u2013177."},{"key":"13_CR37","first-page":"139","volume-title":"LNCS 591","author":"M. Wolfe","year":"1991","unstructured":"Wolfe, M., and Srinivasan, H. Data structures for optimizing programs with explicit parallelism. In Proceedings of the 1\n                st\n                International Conference of the Austrian Center for Parallel Computation, Salzburg, Austria, Springer-Verlag, LNCS 591 (1991), 139\u2013156."}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60630-0_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:26:36Z","timestamp":1619573196000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60630-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540606307","9783540485094"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-60630-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}