Observations About the Development of Theoretical Computer Science
- 1 January 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Annals of the History of Computing
- Vol. 3 (1) , 42-51
- https://doi.org/10.1109/mahc.1981.10005
Abstract
This paper gives a personal account of some early developments in automata theory and the initiation of research in computational complexity theory. Although the account is subjective and deals primarily with the research areas of direct interest to the author, It discusses the underlying beliefs and philosophy that guided this research as well as the intellectual environment and the Ideas and contacts that influenced it. An attempt is also made to draw some general conclusions about computer science research and to discuss the nature of theoretical computer science.Keywords
This publication has 18 references indexed in Scilit:
- Easy constructions in complexity theory: Gap and speed-up theoremsProceedings of the American Mathematical Society, 1973
- An Overview of the Theory of Computational ComplexityJournal of the ACM, 1971
- Methods of the algebraic theory of machinesJournal of Computer and System Sciences, 1967
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Real time computationIsrael Journal of Mathematics, 1963
- Real-Time Computation and Recursive Functions Not Real-Time ComputableIEEE Transactions on Electronic Computers, 1962
- On the State Assignment Problem for Sequential Machines IIIEEE Transactions on Electronic Computers, 1961
- Aufzählbarkeit, Entscheidbarkeit, BerechenbarkeitPublished by Springer Nature ,1961
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959