On the computational complexity of algorithms
HTML articles powered by AMS MathViewer
- by J. Hartmanis and R. E. Stearns
- Trans. Amer. Math. Soc. 117 (1965), 285-306
- DOI: https://doi.org/10.1090/S0002-9947-1965-0170805-7
- PDF | Request permission
References
- A. M. Turing, On computable numbers, with applications to the Entscheidungs problem, Proc. London Math. Soc. (2) 42 (1937), 230-265.
- Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208
- Hisao Yamada, Real-time computation and recursive functions not real-time computable, IRE Trans. EC-11 (1962), 753–760. MR 0152161, DOI 10.1109/TEC.1962.5219459 J. Myhill, Linear bounded automata, WADD Tech. Note 60-165, Rep. No. 60-22, Univ. of Pennsylvania, June, 1960.
- Robert W. Ritchie, Classes of predictably computable functions, Trans. Amer. Math. Soc. 106 (1963), 139–173. MR 158822, DOI 10.1090/S0002-9947-1963-0158822-2
- Noam Chomsky, On certain formal properties of grammars, Information and Control 2 (1959), 137–167. MR 105365, DOI 10.1016/S0019-9958(59)90362-6 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.
- Michael O. Rabin, Real time computation, Israel J. Math. 1 (1963), 203–211. MR 163849, DOI 10.1007/BF02759719
Bibliographic Information
- © Copyright 1965 American Mathematical Society
- 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