Now showing items 15-34 of 56

• #### New Developments in Structural Complexity Theory ﻿

(Cornell University, 1988-04)
This paper discusses the scope and goals of structural complexity theory, describes some working hypothesis of this field and summarizes (some) recent development.
• #### A Note on Natural Creative Sets and Goedel Numberings ﻿

(Cornell University, 1980-01)
Creative sets (or the complete recursively enumerable sets) play an important role in logic and mathematics and they are known to be recursively isomorphic. Therefore, on the one hand, all the creative sets can be viewed ...
• #### A Note on One-way and Two-way Automata ﻿

(Cornell University, 1969-09)
The purpose of this note is to show that there exist non-regular languages whose memory requirements for recognition by one-way and two-way automata differ by a double exponential and that this difference cannot be exceeded.
• #### A Note on Tape Bounds for SLA Language Processing ﻿

(Cornell University, 1975-05)
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 ...
• #### Observations About the Development of Theoretical Computer Science ﻿

(Cornell University, 1980-01)
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 ...
• #### On Census Complexity and Sparseness of NP Complete Sets ﻿

(Cornell University, 1980-04)
In this note we show that if there are sparse NP complete sets with a polynomial time computable census function then $P=NP$. We also derive related results about the complexity of the census function for context-sensitive ...
• #### On Complete Problems for NP$\cap$CoNP ﻿

(Cornell University, 1985-04)
• #### On the Power of Multiplication in Random Access Machines ﻿

(Cornell University, 1974-09)
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 ...