Constant time factors do matter

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constant time factors do matter

Full text

Pdf (836 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 602 - 611

Year of Publication: 1993

ISBN:0-89791-591-7

Author

Neil D. Jones

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, Citation Count: 8

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/167088.167244 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.

	1	T. A. Hansen , T. Nikolajsen , J. L. Träff , N. D. Jones, Experiments with implementations of two theoretical constructions, Logic at Botik'89 Symposium on logical foundations of computer science, Springer-Verlag New York, Inc., New York, NY, 1989
	2	Hendrik Pieter Barendregt , Marko C. J. D. van Eekelen , John R. W. Glauert , Richard Kennaway , Marinus J. Plasmeijer , M. Ronan Sleep, Term Graph Rewriting, Proceedings of the Parallel Architectures and Languages Europe, Volume I, p.141-158, June 15-19, 1987
	3	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	4	J. Royer and J. Case: lntensional subrecursion and complexity theory. Research notes in theoretical science. Pitman Press 1988.
	5	Y. Gurevich , S. Shelah, Nearly linear time, Logic at Botik'89 Symposium on logical foundations of computer science, Springer-Verlag New York, Inc., New York, NY, 1989
	6	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	7	N.D. Jones, S. Muchnick:Flow analysis and optimization of Lisp-like structures. Program Flow Analysss, eds. N.D. Jones, S. Muchnick, pp. 102-131. Prentice-Hall, New Jersey, 1981.
	8	N.D. Jones, P. Sestoft, and H. Scndergaard. Mix: A selfapplicable partial evaluator for experiments in compiler generation. Lssp and Symbolsc Computatson, 2(1):9-50, 1989
	9	Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	10	Stephen Cole Kleene: Introduction to Metamathematics. North-Holland, 1952.
	11	Donald Knuth: Fundamental algorithhms. Addison- Wesley, 1968
	12	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	13	A. SchSnhage: Storage modification machines SIAM Journal of Computing vol. 9, pp. 492-508, 1980.
	14	Robert Tarjan: A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences vol. 18, pp. 110-127, 1979.

CITED BY 8

	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
	Torben æ. Mogensen, Linear-Time Self-Interpretation of the Pure Lambda Calculus, Higher-Order and Symbolic Computation, v.13 n.3, p.217-237, Sept. 2000
	Neil D. Jones, Mix ten years later, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.24-38, June 21-23, 1995, La Jolla, California, United States
	David Sands , Jörgen Gustavsson , Andrew Moran, Lambda calculi and linear speedups, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	Amir M. Ben-Amram, Tighter constant-factor time hierarchies, Information Processing Letters, v.87 n.1, p.39-44, 16 July 2003
	Amir M. Ben-Amram, What is a “pointer machine”?, ACM SIGACT News, v.26 n.2, p.88-95, June 1995
	Kenneth W. Regan, Machine models and linear time complexity, ACM SIGACT News, v.24 n.3, p.5-15, Oct. 1993
	Andrea Asperti, The intensional content of Rice's theorem, ACM SIGPLAN Notices, v.43 n.1, January 2008