JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing Hartmanis, Juris by Issue Date
Now showing items 120 of 56

Computational Complexity of OneTape Turing Machine Computations
Hartmanis, Juris (Cornell University, 196801)This paper is concerned with the quantitative aspects of onetape Turing machine computations. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets ... 
On the Recognition of Primes by Automata
Hartmanis, Juris; Shank, H. (Cornell University, 196802)A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of primes can be accepted by a ... 
Tape Reversal Bounded Turing Machine Computations
Hartmanis, Juris (Cornell University, 196802)This paper studies the classification of recursive sets by the number of tape reversals required for their recognition on a twotape Turing machine with a oneway input tape. This measure yields a rich hierarchy of tape ... 
Two Memory Bounds for the Recognition of Primes by Automata
Hartmanis, Juris; Shank, H. (Cornell University, 196806)Two Memory Bounds for the Recognition of Primes by Automata 
Refinement of Hierarchies of Time Bounded Computations
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 196806)It is shown that for any "slowly growing" time function $T(n)$ and any $\epsilon > 0$ there exists a computation which can be performed by a multitape Turing machine in time $T(n)\log^{\epsilon}T(n)$ and cannot be performed ... 
A Note on Oneway and Twoway Automata
Hartmanis, Juris (Cornell University, 196909)The purpose of this note is to show that there exist nonregular languages whose memory requirements for recognition by oneway and twoway automata differ by a double exponential and that this difference cannot be exceeded. 
The Use of Lists in the Study of Undecidable Problems in Automata Theory
Hartmanis, Juris; Lewis, Forbes (Cornell University, 197001)NO ABSTRACT SUPPLIED 
An Overview of the Theory of Computational Complexity
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 197004)The purpose of this paper is to outline the theory of computational complexity which has emerged as a comprehensive theory during the last decade. This theory is concerned with the quantitative aspects of computations and ... 
Computational Complexity of Random Access Stored Program Machines
Hartmanis, Juris (Cornell University, 197008)In this paper we explore the computational complexity measure defined by running times of programs on random access stored program machines, RASP'S. The purpose of this work is to study more realistic complexity measures ... 
Size Arguments in the Study of Computation Speeds
Hartmanis, Juris (Cornell University, 197008)In this paper we use arguments about the size of the computed functions to investigate the computation speed of Turing machines. It turns out that the size arguments yield several new results which we have not been able ... 
Final Report on NSF Research Grant Automata and Computational Complexity 19681972
Hartmanis, Juris (Principal Investigator) (Cornell University, 197208)This report summarizes the results obtained in research supported by the National Science Foundation Grant AUTOMATA AND COMPUTATIONAL COMPLEXITY. The report lists the problem areas considered, the publications resulting ... 
The LBA Problem and its Importance in the Theory of Computing
Hartmanis, Juris; Hunt, Harry B., III (Cornell University, 197305)In this paper we study the classic problem of determining whether the deterministic and nondeterministic contextsensitive languages are the same or, equivalently, whether the languages accepted by deterministic and ... 
On the Problem of Finding Natural Computational Complexity Measures
Hartmanis, Juris (Cornell University, 197306)To develop an abstract theory which deals with the quantitative aspects of computing we need a deeper understanding of how to define "natural" computational complexity measures axiomatically. To this end, this paper ... 
On Simple Goedel Numberings and Translations
Hartmanis, Juris; Baker, Theodore Paul (Cornell University, 197307)In this paper we consider Goedel numberings (viewed as simple models for programming languages) into which all other Goedel numberings can be translated very easily. Several such classes of Goedel numberings are defined ... 
Computational Complexity of Formal Translations
Hartmanis, Juris (Cornell University, 197312)The purpose of this paper is to define a mathematical model for the study of quantitative problems about translations between universal languages and to investigate such problems. The results derived in this paper deal ... 
On the Structure of Feasible Computations
Hartmanis, Juris; Simon, Janos (Cornell University, 197408)During the last four years research on the lower level computational complexity has yielded a rich set of interesting results which have revealed deep and unexpected connections between various problems and thus brought ... 
On the Power of Multiplication in Random Access Machines
Hartmanis, Juris; Simon, Janos (Cornell University, 197409)We consider random access machines with a multiplication operation, having the added capability of computing logical operations on bit vectors in parallel. The contents of a register are considered both as an integer and ... 
A Note on Tape Bounds for SLA Language Processing
Hartmanis, Juris; Berman, L. (Cornell University, 197505)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 ... 
On Effective Speedup and Long Proofs of Trivial Theorems in Formal Theories
Hartmanis, Juris (Cornell University, 197507)In this note we give a very simple proof which shows that in many interesting formal mathematical theories, axiomatizable as well as decidable ones, for every given formalization we can effectively find infinite subsets ... 
On Isomorphisms and Density of NP and Other Complete Sets
Hartmanis, Juris; Berman, L. (Cornell University, 197510)If all NP complete sets are isomorphic under deterministic polynomial time mappings (pisomorphic) then P $\neq$ NP and if all PTAPE complete sets are pisomorphic then P $\neq$ PTAPE. We show that all NP complete sets ...