JavaScript is disabled for your browser. Some features of this site may not work without it.
Computer Science Technical Reports
Browse by
This is a collection of technical reports from the Cornell's Computer Science (CS) Department from the time period of 19682002. These reports are part of the NCSTRL collection of Computer Science Technical Reports.
For reports from 2003present, see the Computing and Information Science Technical Reports Collection.
Recent Submissions

FlowLimited Authorization
Arden, Owen; Liu, Jed; Myers, Andrew (20150508)Because information flow control mechanisms often rely on an underlying authorization mechanism, their security guarantees can be subverted by weaknesses in authorization. Conversely, the security of authorization can ... 
A Linear List Merging Algorithm
Hopcroft, John E.; Ullman, Jeffrey D. (20080514)A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and to find the name of ... 
On the Modelling Power of Petri Nets
Meiling, Erik (Cornell University, 197912)The behavior of a Petri net is expressed as a formal language. Certain families of Petri net languages are characterized by propositions similar to the classical pumping theorems. The results are used to give examples ... 
Cand and Cor Before and Then or Else in Ada
Gries, David (Cornell University, 197911)NO ABSTRACT SUPPLIED 
A Proof Technique for Communicating Sequential Processes(With an Example)
Levin, Gary Marc (Cornell University, 197911)We present proof rules for an extension of the Communicating Sequential Processes proposed by Hoare. The send and receive statements are treated symmetrically, simplifying the rules and allowing send to appear in guards. ... 

The System Architecture for CORE: A Tolerant Program Development Environment
Archer, James E., Jr.; Conway, Richard W.; Shore, Andrew I.; Silver, Leonard S. (Cornell University, 197910)CORE is a program development environment intended primarily to explore a highly tolerant useer interface. In some respects the internal architecture is also novel. It permits a highly interactive and supportive user ... 
A Program Development System Execution Supervisor
Archer, James E., Jr.; Shore, Andrew I. (Cornell University, 197910)The Cornell Program Development System is an experimental vehicle to explore the applicability of highly cooperative tactics to a contemporary development environment. The CPDS provides significant facilities for modifying ... 
Quadratic Programming with MMatrices
Luk, Franklin T.; Pagano, Marcello (Cornell University, 197910)In this paper, we study the problem of quadratic programming with Mmatrices. We describe (1) an effective algorithm for the case where the variables are subject to a lower bound constraint, and (2) an analogous algorithm ... 
Ada/CS  An Instructional Subset of the Programming Language Ada
Archer, James E., Jr. (Cornell University, 197910)NO ABSTRACT SUPPLIED 

Efficient OnLine Construction and Correction of Position Trees
Majster, Mila E. (Cornell University, 197910)This paper presents an online algorithm for the construction of position trees, i.e. an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an online ... 
Ensuring Consistency in a Distributed Database System by Use of Distributed Semaphores
Schneider, Fred B. (Cornell University, 197909)Solutions to the database consistency problem in distributed databases are developed. It is shown how any solution to the consistency problem for a centralized database system that involves locking can be adapted for use ... 
Synchronization in Distributed Programs
Schneider, Fred B. (Cornell University, 197909)A technique for solving synchronization problems in distributed programs is described. Use of this technique in environments in which processes may fail is discussed. The technique can be used to solve synchronization ... 
On Easily Infinite Sets and On a Statement of R. Lipton
Leivant, Daniel (Cornell University, 197909)For a complexity measure $\kappa$, a set is $\kappa$infinite if it contains a $\kappa$decidable infinite subset. For a timebased $\kappa$, we prove that there is a recursive S s.t. both S and its complements, $\bar{S}$, ... 
A Logic For Correct Program Development
Bates, Joseph Louis (Cornell University, 197908) 
The Complexity of Parallel Computations
Wyllie, James C. (Cornell University, 197908)Recent advances in microelectronics have brought closer to feasibility the construction of computers containing thousands (or more) of processing elements. This thesis addresses the question of effective utilization of ... 
A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem
Dietz, Paul F.; Furst, Merrick; Hopcroft, John E. (Cornell University, 197907)THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for efficient retrieval. A ... 
A TimeSpace Tradeoff for InPlace Array Permutation
Melville, Robert C. (Cornell University, 197907)NO ABSTRACT SUPPLIED 
Convergence Theorems for Least Change Secant Update Methods
Dennis, John E. Jr.; Walker, Homer F. (Cornell University, 197907)The purpose of this paper is to present a convergence analysis of the least change secant methods in which part of the derivative matrix being approximated is computed by other means. The theorems and proofs given here ...