{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:31Z","timestamp":1725663751052},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540557197"},{"type":"electronic","value":"9783540472780"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55719-9_100","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T05:35:53Z","timestamp":1330234553000},"page":"509-520","source":"Crossref","is-referenced-by-count":4,"title":["On the complexity of dataflow analysis of logic programs"],"prefix":"10.1007","author":[{"given":"Saumya K.","family":"Debray","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"issue":"no.4","key":"42_CR1","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1145\/1634.1639","volume":"31","author":"P. A. Bloniarz","year":"1984","unstructured":"P. A. Bloniarz, H. B. Hunt III, and D. J. Rosenkrantz, \u201cAlgebraic Structures with Hard Equivalence and Minimization Problems\u201d, J. ACM vol. 31 no. 4, Oct. 1984, pp. 879\u2013904.","journal-title":"J. ACM"},{"key":"42_CR2","unstructured":"M. Bruynooghe, \u201cCompile time Garbage Collection\u201d, Proc. IFIP Working Conference on Program Transformation and Verification, Elsevier, 1986."},{"key":"42_CR3","unstructured":"J.-H. Chang, A. M. Despain, and D. DeGroot, \u201cAND-Parallelisrn of Logic Programs Based on A Static Data Dependency Analysis\u201d, in Digest of Papers, Compcon 85, IEEE Computer Society, Feb. 1985, pp. 218\u2013225."},{"key":"42_CR4","volume-title":"Technical Report CS90-10","author":"M. Codish","year":"1990","unstructured":"M. Codish, D. Dams, and Y. Yardeni, \u201cAbstract Unification and a Bottom-up Analysis to Detect Aliasing in Logic Programs\u201d, Technical Report CS90-10, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel, May 1990."},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"S. A. Cook, \u201cThe Complexity of Theorem-proving Procedures\u201d, Proc. Third ACM Symposium on Theory of Computing, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"P. Cousot and R. Cousot, \u201cAbstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Apporoximation of Fixpoints\u201d, Proc. Fourth ACM Symposium on Principles of Programming Languages, 1977, pp. 238\u2013252.","DOI":"10.1145\/512950.512973"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"P. Cousot, and R. Cousot, \u201cSystematic Design of Program Analysis Frame-works\u201d, Proc. Sixth ACM Symposium on Principles of Programming Languages, 1979, pp. 269\u2013282.","DOI":"10.1145\/567752.567778"},{"issue":"no.3","key":"42_CR8","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0743-1066(88)90010-6","volume":"5","author":"S. K. Debray","year":"1988","unstructured":"S. K. Debray and D. S. Warren, \u201cAutomatic Mode Inference for Logic Programs\u201d, J. Logic Programming vol. 5 no. 3 (Sept. 1988), pp. 207\u2013229.","journal-title":"J. Logic Programming"},{"issue":"no.3","key":"42_CR9","first-page":"419","volume":"11","author":"S. K. Debray","year":"1989","unstructured":"S. K. Debray, \u201cStatic Inference of Modes and Data Dependencies in Logic Programs\u201d, ACM Transactions on Programming Languages and Systems vol. 11 no. 3, July 1989, pp. 419\u2013450.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"42_CR10","unstructured":"S. K. Debray, \u201cEfficient Dataflow Analysis of Logic Programs\u201d, J. ACM (to appear)."},{"key":"42_CR11","volume-title":"Technical Report TR 91-27","author":"S. K. Debray","year":"1991","unstructured":"S. K. Debray, \u201cOn the Complexity of Dataflow Analysis of Logic Programs\u201d, Technical Report TR 91-27, Dept. of Computer Science, The University of Arizona, Tucson, AZ 85721, USA, Dec. 1991."},{"key":"42_CR12","unstructured":"W. Drabent, \u201cDo Logic Programs Resemble Programs in Conventional Languages?\u201d, Proc. IEEE Symposium on Logic Programming, San Francisco, CA, Aug. 1987, pp. 389\u2013396."},{"key":"42_CR13","volume-title":"Research Report RC-16089","author":"N. Heintze","year":"1990","unstructured":"N. Heintze and J. Jaffar, \u201cA Finite Presentation Theorem for Approximating Logic Programs\u201d, Research Report RC-16089, IBM T. J. Watson Research Center, Yorktown Heights, August 1990. (Preliminary version appeared in Proc. Seventeenth ACM Symposium on Principles of Programming Languages, Jan. 1990.)"},{"key":"42_CR14","volume-title":"Technical Report CMU-CS-91-110","author":"N. Heintze","year":"1991","unstructured":"N. Heintze and J. Jaffar, \u201cA Decision Procedure for a Class of Set Constraints\u201d, Technical Report CMU-CS-91-110, School of Computer Science, Carnegie Mellon University, Pittsburgh, February 1991. (Preliminary version appeared in Proc. Fifth IEEE Symposium on Logic in Computer Science.)"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"P. Hudak and J. Young, \u201cHigher-Order Strictness Analysis in the Untyped Lambda Calculus\u201d, Proc. Thirteenth ACM Symp. on Principles of Programming Languages, Jan. 1986.","DOI":"10.1145\/512644.512653"},{"key":"42_CR16","unstructured":"D. Jacobs and A. Langen, \u201cAccurate and Efficient Approximation of Variable Aliasing in Logic Programs\u201d, Proc. North American Conference on Logic Programming, Cleveland, Ohio, Oct. 1989, pp. 154\u2013165."},{"key":"42_CR17","volume-title":"PhD Dissertation","author":"G. Janssens","year":"1990","unstructured":"G. Janssens, \u201cDeriving Run-time Properties of Logic Programs by means of Abstract Interpretation\u201d, PhD Dissertation, Dept. of Computer Science, Katholieke Universiteit Leuven, Belgium, March 1990."},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"N. D. Jones and S. S. Muchnick, \u201cComplexity of Flow Analysis, Inductive Assertion Synthesis, and a Language due to Dijkstra\u201d, in Program Flow Analysis: Theory and Applications, eds. S. S. Muchnick and N. D. Jones, Prentice Hall, 1981, pp. 381\u2013393.","DOI":"10.1109\/SFCS.1980.16"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"J. W. Lloyd, Foundations of Logic Programming, Springer Verlag, 1984.","DOI":"10.1007\/978-3-642-96826-6"},{"key":"42_CR20","unstructured":"H. Mannila and E. Ukkonen, \u201cFlow Analysis of Prolog Programs\u201d, Proc. Fourth IEEE Symposium on Logic Programming, San Francisco, CA, Sept. 1987."},{"key":"42_CR21","unstructured":"K. Marriott, H. S\u00f8ndergaard and N. D. Jones, \u201cDenotational Abstract Interpretation of Logic Programs\u201d, Manuscript, Dept. of Computer Science, University of Melbourne, May 1990."},{"key":"42_CR22","unstructured":"K. Marriott and H. S\u00f8ndergaard, personal communication, March 1991."},{"issue":"no.1","key":"42_CR23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0743-1066(85)90004-4","volume":"2","author":"C. S. Mellish","year":"1985","unstructured":"C. S. Mellish, \u201cSome Global Optimizations for a Prolog Compiler\u201d, J. Logic Programming vol. 2 no. 1 (Apr. 1985), pp. 43\u201366.","journal-title":"J. Logic Programming"},{"key":"42_CR24","unstructured":"P. Mishra, \u201cTowards a Theory of Types for Prolog\u201d, Proc. IEEE Symposium on Logic Programming, Atlantic City, 1984, pp. 289\u2013298."},{"key":"42_CR25","unstructured":"A. Mulkers, W. Winsborough and M. Bruynooghe, \u201cAnalysis of Shared Data Structures for Compile-Time Garbage Collection in Logic Programs\u201d, Proc. Seventh International Conference on Logic Programming, Jerusalem, Israel, June 1990, pp. 747\u2013764."},{"key":"42_CR26","unstructured":"K. Muthukumar and M. Hermenegildo, \u201cDetermination of Variable Dependence Information at Compile Time through Abstract Interpretation\u201d, Proc. North American Conference on Logic Programming, Cleveland, Ohio, Oct. 1989, pp. 166\u2013185."},{"key":"42_CR27","unstructured":"K. Muthukumar and M. Hermenegildo, \u201cCombined Determination of Sharing and Freeness of Program Variables through Abstract Interpretation\u201c, Proc. Eighth International Conference on Logic Programming, Paris, June 1991, pp. 49\u201363."},{"key":"42_CR28","doi-asserted-by":"crossref","unstructured":"E. W. Myers, \u201cA Precise Inter-procedural Data Flow Algorithm\u201d, Proc. Eighth ACM Symposium on Principles of Programming Languages, 1981, pp. 219\u2013230.","DOI":"10.1145\/567532.567556"},{"key":"42_CR29","first-page":"321","volume-title":"Top-down vs. Bottom-up Revisited","author":"R. Ramakrishnan","year":"1991","unstructured":"R. Ramakrishnan and S. Sudarshan, \u201cTop-down vs. Bottom-up Revisited\u201d, Proc. 1991 International Symposium on Logic Programming, San Diego, Oct. 1991, pp. 321\u2013336. MIT Press."},{"key":"42_CR30","volume-title":"Technical Report STAN-CS-84-1009","author":"Y. Sagiv","year":"1984","unstructured":"Y. Sagiv and J. D. Ullman, \u201cComplexity of a Top-Down Capture Rule\u201d, Technical Report STAN-CS-84-1009, Dept. of Computer Science, Stanford University, Stanford, CA, July 1984."},{"key":"42_CR31","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0304-3975(84)90119-1","volume":"34","author":"T. Sato","year":"1984","unstructured":"T. Sato and H. Tamaki, \u201cEnumeration of Success Patterns in Logic Programs\u201d, Theoretical Computer Science 34 (1984), pp. 227\u2013240.","journal-title":"Theoretical Computer Science"},{"key":"42_CR32","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer, \u201cWord Problems requiring Exponential Time\u201d, Proc. Fifth ACM Symposium on Theory of Computing, 1973, pp. 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"42_CR33","doi-asserted-by":"crossref","unstructured":"S.-\u00c5. T\u00e4rnlund, \u201cHorn Clause Computability\u201d, BIT IT, pp. 215\u2013226.","DOI":"10.1007\/BF01932293"},{"key":"42_CR34","doi-asserted-by":"crossref","unstructured":"J. D. Ullman, \u201cThe Complexity of Ordering Subgoals\u201d, Proc. Seventh ACM Symposium on Principles of Database Systems, Austin, TX, March 1988, pp. 74\u201381.","DOI":"10.1145\/308386.308417"},{"key":"42_CR35","doi-asserted-by":"crossref","unstructured":"Ullman, J.D., \u201cBottom-Up Beats Top-Down for Datalog\u201d, In Proceedings of the ACM Symposium on Principles of Database Systems, pages 140\u2013150, Philadelphia, PA, 1989.","DOI":"10.1145\/73721.73736"},{"key":"42_CR36","unstructured":"E. Yardeni and E. Shapiro, \u201cA Type System for Logic Programs\u201d, in Concurrent Prolog: Collected Papers, vol. 2, ed. E. Shapiro, pp. 211\u2013244."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55719-9_100.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:01:31Z","timestamp":1605628891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55719-9_100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557197","9783540472780"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-55719-9_100","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}