Search For:

Displaying 1-19 out of 19 total
A note on tape bounds for sla language processing
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis, L. Berman
Issue Date:October 1975
pp. 65-70
In this note we show that the tape bounded complexity classes of languages over single letter alphabets are closed under complementation. We then use this result to show that there exists an infinite hierarchy of tape bounded complexity classes of sla lang...
 
Structure of undecidable problems in automata theory
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis, J. E. Hopcroft
Issue Date:October 1968
pp. 327-333
The purpose of this paper is to gain a better understanding of the structure of undecidable problems in automata theory by investigating the degree of unsolvability of these problems. This is achieved by using Turing machines with oracles to define when on...
 
Observations about the development of theoretical computer science
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis
Issue Date:October 1979
pp. 224-233
This paper gives a personal account of some developments in automata theory and computational complexity theory. Though the account is subjective and deals primarily with the research areas of direct interest to the author, it discusses the underlying beli...
 
Computational complexity of recursive sequnces
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis, R. E. Stearns
Issue Date:November 1964
pp. 82-90
In this paper we investigate how numbers, functions, and sequences can be classified according to their computational complexity. The computational complexity is measured by how fast the number or function can be computed by a multitape computer (Turing ma...
 
One-way log-tape reductions
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis, N. Immerman, S. Mahaney
Issue Date:October 1978
pp. 65-72
One-way log-tape (1-L) reductions are mappings defined by log-tape Turing machines whose read head on the input can only move to the right. The 1-L reductions provide a more refined tool for studying the feasible complexity classes than the P-time [2,7] or...
 
R70-1 A Note on Computing Time for the Recognition of Context- Free Languages by a Single-Tape Turing Machine
Found in: IEEE Transactions on Computers
By J. Hartmanis
Issue Date:May 1970
pp. 463
Although considerable progress has been made in the understanding of the more
   
On the application of pair algebra to automata theory
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, J. Hartmanis
Issue Date:November 1964
pp. 192-196
In this paper, we define and discuss generalizations of partition pairs on sequential machines. The object of these generalizations is to suggest a unified approach to problems of information flow and machine structure.
 
An Overview of the Theory of Computational Complexity
Found in: Journal of the ACM (JACM)
By J. E. Hopcroft, J. Hartmanis
Issue Date:July 1971
pp. 444-475
Many problems, some of them quite meaningful, have been proved to be recursively unsolvable for programs in general. The paper is directed toward a class of programs where many decision problems are solvable. The equivalence problem has been proved to be u...
     
On the complexity of undecidable problems in automata theory
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis
Issue Date:October 1967
pp. 112-116
This paper describes some general results about hierarchies of undecidable problems in automata theory, and studies how properties of sets accepted by automata change from decidable to undecidable problems as the memory capacity of the automaton is increas...
 
Hierarchies of memory limited computations
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, J. Hartmanis, P. M. Lewis
Issue Date:October 1965
pp. 179-190
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A
 
Memory bounds for recognition of context-free and context-sensitive languages
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By P. M. Lewis, R. E. Stearns, J. Hartmanis
Issue Date:October 1965
pp. 191-202
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A
 
The Cornell commission: on Morris and the worm
Found in: Communications of the ACM
By D. Gries, D. Holcomb, J. Hartmanis, M. S. Lynn, T. Eisenberg, T. Santoro
Issue Date:January 1988
pp. 706-709
After careful examination of the evidence, the Cornell commission publishes its findings in a detailed report that sheds new light and dispels some myths about Robert T. Morris and the Internet worm.
     
Sparse sets in NP-P: Exptime versus nexptime
Found in: Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83)
By J. Hartmanis, N. Immerman, V. Sewelson
Issue Date:December 1983
pp. 382-391
This paper investigates the structural properties of sets in NP-P and shows that the computational difficulty of lower density sets in NP depends explicitly on the relations between higher deterministic and nondeterministic time-bounded complexity classes....
     
Relations between diagonalization, proof systems, and complexity gaps
Found in: Proceedings of the ninth annual ACM symposium on Theory of computing (STOC '77)
By J. Hartmanis
Issue Date:May 1977
pp. 223-227
In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional R...
     
On isomorphisms and density of NP and other complete sets
Found in: Proceedings of the eighth annual ACM symposium on Theory of computing (STOC '76)
By J. Hartmanis, L. Berman
Issue Date:May 1976
pp. 30-40
If all NP complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then P @@@@ NP and if all PTAPE complete sets are p-isomorphic then P @@@@ PTAPE. We show that all NP complete sets known (in the literature) are indeed p-is...
     
Complexity of formal translations and speed-up results
Found in: Proceedings of the third annual ACM symposium on Theory of computing (STOC '71)
By J. Hartmanis, R. L. Constable
Issue Date:May 1971
pp. 244-250
The purpose of this paper is to give a model for the study of quantitative problems about formal translations from one programming language into another, as well as derive some initial results about the speed of programs produced by translations. The paper...
     
On the Complexity of Undecidable Problems in Automata Theory
Found in: Journal of the ACM (JACM)
By J. Hartmanis
Issue Date:January 1969
pp. 160-167
Some general results about hierarchies of undecidable problems in automata theory are given, and studies are described which show how properties of sets accepted by automata (i.e. languages) change from decidable to undecidable problems as the computationa...
     
Computational Complexity of One-Tape Turing Machine Computations
Found in: Journal of the ACM (JACM)
By J. Hartmanis
Issue Date:April 1968
pp. 325-339
The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets of sequences. It is shown that the computation tim...
     
On Memory Requirements for Context-Free Language Recognition
Found in: Journal of the ACM (JACM)
By J. Hartmanis
Issue Date:October 1967
pp. 663-665
The purpose of this note is to show that it is recursively undecidable how much tape is required by a Turing machine to recognize nonregular context-free languages.
     
 1