Computational Work and Time on Finite Machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational Work and Time on Finite Machines

Full text

Pdf (976 KB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 4 (October 1972) table of contents

Pages: 660 - 674

Year of Publication: 1972

ISSN:0004-5411

Author

J. E. Savage

Brown University, Division of Engineering, Providence, Rhode Island

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 31, Citation Count: 11

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/321724.321731 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	Marvin Minsky, Form and Content in Computer Science (1970 ACM turing lecture), Journal of the ACM (JACM), v.17 n.2, p.197-215, April 1970 [doi>10.1145/321574.321575]
	2	SAVAGE, J. E. Three measures of decoder complexity. IBM J. Res. Devel. 15, 4, (July 1970), 417-425.
	3	SAVAGE, J. E. The complexity of decoders--Part II: Computational work and decoding time. IEEE Trans. on Information Theory, IT-17, 1, (Jan., 1971). 77-85.
	4	S. Winograd, On the Time Required to Perform Addition, Journal of the ACM (JACM), v.12 n.2, p.277-285, April 1965 [doi>10.1145/321264.321279]
	5	S. Winograd, On the Time Required to Perform Multiplication, Journal of the ACM (JACM), v.14 n.4, p.793-802, Oct. 1967 [doi>10.1145/321420.321438]
	6	HARRISON, M. A. Introduction to Switching and Automata Theory. McGraw-Hill, New York, 1965, Ch. 6, 7.
	7	YOUNGER, D.H. Recognition and parsing of context-free languages in time n 3. Information and Control I0, 2, (1967), 189-208.

CITED BY 11

	Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States
	Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979
	D A Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.1-5, May 28-30, 1986, Berkeley, California, United States
	Richard Ladner , Nancy Lynch , Alan Selman, Comparison of polynomial-time reducibilities, Proceedings of the sixth annual ACM symposium on Theory of computing, p.110-121, April 30-May 02, 1974, Seattle, Washington, United States
	Michael C. Loui, Strategic directions in research in theory of computing, ACM Computing Surveys (CSUR), v.28 n.4, p.575-590, Dec. 1996
	Michael Sipser, The history and status of the P versus NP question, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.603-618, May 04-06, 1992, Victoria, British Columbia, Canada
	Larry Stockmeyer , Albert R. Meyer, Cosmological lower bound on the circuit complexity of a small problem in logic, Journal of the ACM (JACM), v.49 n.6, p.753-784, November 2002
	Jiří Šíma , Pekka Orponen, General-purpose computation with neural networks: a survey of complexity theoretic results, Neural Computation, v.15 n.12, p.2727-2778, December 2003
	Harumichi Nishimura , Tomoyuki Yamakami, Polynomial time quantum computation with advice, Information Processing Letters, v.90 n.4, p.195-204, 31 May 2004
	Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002
	G. R. Kiss, Outlines of a computer model of motivation, Proceedings of the 3rd international joint conference on Artificial intelligence, p.446-449, August 20-23, 1973, Stanford, USA