Automatic complexity analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Automatic complexity analysis

Full text

Pdf (1.24 MB)

Source

Functional Programming Languages and Computer Architecture archive
Proceedings of the fourth international conference on Functional programming languages and computer architecture table of contents

Imperial College, London, United Kingdom

Pages: 144 - 156

Year of Publication: 1989

ISBN:0-89791-328-0

Author

Mads Rosendahl

Computer Laboratory, University of Cambridge, Cambridge CB2 3QG, England

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IFIP WG 2.8 : IFIP WG 2.8
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 37, Citation Count: 32

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/99370.99381 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Adachi, Kasai & Moriya 1979	Akeo Adachi, Takumi Kazai, and Etsuro Moriya. A TAcorctieal Study on the Time Analysis of Programs. Lecture Notes in Computer Science, vol. 74, pp. 201-207. Springer-Verlag, 1979.
	Aho, Hopcroft & Ullman 1974	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	Cohen & Katcoff 1977	Jacques Cohen , Joel Katcoff, Symbolic Solution of Finite-Difference Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.261-271, Sept. 1977 [doi>10.1145/355744.355751]
	Cohen 1982	Jacques Cohen, Computer-assisted microanalysis of programs, Communications of the ACM, v.25 n.10, p.724-733, Oct 1982 [doi>10.1145/358656.358674]
	Cousot & Cousot 1977	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	Flajolet 1987	P. Flajolet. Mathematical Tools for Antomatic Program Analltzis. Technical Report 603. Institut National de Recherche en Informatique et en Automatiqtte, February, 1987.
	Gordon 1979	Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
	Hickey & Cohen 1988	Timothy Hickey , Jacques Cohen, Automating program analysis, Journal of the ACM (JACM), v.35 n.1, p.185-220, Jan. 1988 [doi>10.1145/42267.42275]
	Kazai et al 1980	Kazai et al. An Automatic Time Analysis $~stem. Technical Report RIMS-335. Kyoto University, May, 1980.
	Le Métayer 1985	D. Le Metayer, Mechanical analysis of program complexity, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.69-73, June 25-28, 1985, Seattle, Washington, United States
	Le Métayer 1988	Daniel Le Métayer, ACE: an automatic complexity evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.248-266, April 1988 [doi>10.1145/42190.42347]
	McCarthy et al 1965	John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
	Reynolds 1969	John C. Reynolds. Automatic Computation of Data Set Definitions. Information Processing 68, pp. 456--461, 1969.
	Rosendahl 1986	Madz Rozendahl. A~tomatic Program Analysis. Master's Thesis. Institute of Dat. slaty, University of Copenhagen, 1986.
	Sarkar & Hennessy 1986	Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, ACM SIGPLAN Notices, v.21 n.7, p.17-26, July 1986
	Talcott 1986	Carolyn Talcott. Derived properties and de~i~ed programs. Stanford University, May, 1986.
	Turchin 1986	Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
	Wadler 1988	P. Wadler, Strictness analysis aids time analysis, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73571]
	Wegbreit 1975	Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
	Wegbreit 1976	Ben Wegbreit. Goal-Directed Program Transformation. IEEE Transactions on Software Engineering, vol. SF_,-2, no. 2, pp. 69-80, June, 1976.

CITED BY 32

	Vincent Dornic , Pierre Jouvelot , David K. Gifford, Polymorphic time systems for estimating program complexity, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.33-45, March 1992
	Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, ACM SIGPLAN Notices, v.31 n.6, p.213-225, June 15, 1996
	Saumya K. Debray , Nai-Wei Lin , Manuel Hermnegildo, Task granularity analysis in logic programs, ACM SIGPLAN Notices, v.25 n.6, p.174-188, Jun. 1990
	Bernd Grobauer, Cost recurrences for DML programs, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Saumya K. Debray , Nai-Wei Lin, Cost analysis of logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.826-875, Nov. 1993
	Brian Reistad , David K. Gifford, Static dependent costs for estimating execution time, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.65-78, July-Sept. 1994
	Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Discovering auxiliary information for incremental computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-170, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Saumya Debray, Abstract interpretation and low-level code optimization, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.111-121, June 21-23, 1995, La Jolla, California, United States
	Yanhong A. Liu , Tim Teitelbaum, Caching intermediate results for program improvement, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-201, June 21-23, 1995, La Jolla, California, United States
	Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States
	Stephen Brookes , Denis Dancanet, Sequential algorithms, deterministic parallelism, and intensional expressiveness, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.13-24, January 23-25, 1995, San Francisco, California, United States
	John Greiner , Guy E. Blelloch, A provably time-efficient parallel implementation of full speculation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.240-285, March 1999
	Leena Unnikrishnan , Scott D. Stoller , Yanhong A. Liu, Automatic Accurate Live Memory Analysis for Garbage-Collected Languages, ACM SIGPLAN Notices, v.36 n.8, p.102-111, Aug. 2001
	Mads Rosendahl, Simple driving techniques, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Higher-Order and Symbolic Computation, v.16 n.1-2, p.37-62, March-June 2003
	Flemming Nielson , Hanne Riis Nielson, Operational semantics of termination types, Nordic Journal of Computing, v.3 n.2, p.144-187, Summer 1996
	Gustavo Gómez , Yanhong A. Liu, Automatic time-bound analysis for a higher-order language, ACM SIGPLAN Notices, v.37 n.3, p.75-86, March 2002
	Jyh-Herng Chow , William Ludwell Harrison, III, Compile-time analysis of parallel programs that share memory, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 19-22, 1992, Albuquerque, New Mexico, United States
	Ralph Benzinger, Automated higher-order complexity analysis, Theoretical Computer Science, v.318 n.1-2, p.79-103, June 2004
	Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
	Y. A. Liu , G. Gómez, Automatic Accurate Cost-Bound Analysis for High-Level Languages, IEEE Transactions on Computers, v.50 n.12, p.1295-1309, December 2001
	Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998
	E. Albert , P. Arenas , S. Genaim , G. Puebla , D. Zanardini, Experiments in Cost Analysis of Java Bytecode, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.67-83, July, 2007
	Daniel Spoonhower , Guy E. Blelloch , Robert Harper , Phillip B. Gibbons, Space profiling for parallel functional programs, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Simon F. Goldsmith , Alex S. Aiken , Daniel S. Wilkerson, Measuring empirical computational complexity, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia
	Ralph Benzinger, Automated complexity analysis of Nuprl extracted programs, Journal of Functional Programming, v.11 n.1, p.3-31, January 2001
	Sumit Gulwani , Krishna K. Mehra , Trishul Chilimbi, SPEED: precise and efficient static estimation of program computational complexity, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	E. Albert , P. Arenas , S. Genaim , G. Puebla , D. Zanardini, Removing useless variables in cost analysis of Java bytecode, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	James Cheney , Morten Dahl, Resource bound analysis for database queries, Proceedings of the third ACM SIGPLAN workshop on Programming languages and analysis for security, June 07-13, 2008, Tucson, AZ, USA
	Ruy Ley-Wild , Umut A. Acar , Matthew Fluet, A cost semantics for self-adjusting computation, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Leena Unnikrishnan , Scott D. Stoller, Parametric heap usage analysis for functional programs, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	Elvira Albert , Puri Arenas , Samir Genaim , Germán Puebla, Cost Relation Systems: A Language-Independent Target Language for Cost Analysis, Electronic Notes in Theoretical Computer Science (ENTCS), 248, p.31-46, August, 2009