Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the computational complexity of algorithms


Authors: J. Hartmanis and R. E. Stearns
Journal: Trans. Amer. Math. Soc. 117 (1965), 285-306
MSC: Primary 02.80
DOI: https://doi.org/10.1090/S0002-9947-1965-0170805-7
MathSciNet review: 0170805
Full-text PDF Free Access

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] A. M. Turing, On computable numbers, with applications to the Entscheidungs problem, Proc. London Math. Soc. (2) 42 (1937), 230-265.
  • [2] M. Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 0124208 (23:A1525)
  • [3] H. Yamada, Real-time computation and recursive functions not real-time computable, IRE Trans. EC-11 (1962), 753-760. MR 0152161 (27:2141)
  • [4] J. Myhill, Linear bounded automata, WADD Tech. Note 60-165, Rep. No. 60-22, Univ. of Pennsylvania, June, 1960.
  • [5] R. W. Ritchie, Classes of predictably computable functions, Trans. Amer. Math. Soc. 106 (1963), 139-173. MR 0158822 (28:2045)
  • [6] A. N. Chomsky, On certain formal properties of grammars, Information and Control 2 (1959), 137-167. MR 0105365 (21:4107)
  • [7] J. Hartmanis and R. E. Stearns, Computational complexity of recursive sequences, Proc. Fifth Annual Sympos. on Switching Theory and Logical Design, Princeton, N. J. 1964.
  • [8] M. O. Rabin, Real-time computation, Israel J. Math. 1 (1963), 203-211. MR 0163849 (29:1148)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.80

Retrieve articles in all journals with MSC: 02.80


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1965-0170805-7
Article copyright: © Copyright 1965 American Mathematical Society

American Mathematical Society