This is a collection of technical reports from the Cornell's Computer Science (CS) Department from the time period of 1968-2002. These reports are part of the NCSTRL collection of Computer Science Technical Reports.

For reports from 2003-present, see the Computing and Information Science Technical Reports Collection.

Recent Submissions

  • JRIF: Reactive Information Flow Control for Java 

    Kozyri, Elisavet; Arden, Owen; Myers, Andrew C.; Schneider, Fred B. (2015-10-24)
    Classic information flow systems conservatively define the security label associated with a derived value to be at least as restrictive as the security label on any input to that derivation. Because restrictions on information ...
  • Flow-Limited Authorization 

    Arden, Owen; Liu, Jed; Myers, Andrew (2015-05-08)
    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. (2008-05-14)
    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, 1979-12)
    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, 1979-11)
  • A Proof Technique for Communicating Sequential Processes(With an Example) 

    Levin, Gary Marc (Cornell University, 1979-11)
    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. ...
  • On Linear Natural Deduction 

    Leivant, Daniel (Cornell University, 1979-11)
  • 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, 1979-10)
    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, 1979-10)
    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 M-Matrices 

    Luk, Franklin T.; Pagano, Marcello (Cornell University, 1979-10)
    In this paper, we study the problem of quadratic programming with M-matrices. 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, 1979-10)
  • A Unified View of Semantics 

    Majster, Mila E. (Cornell University, 1979-10)
  • Efficient On-Line Construction and Correction of Position Trees 

    Majster, Mila E. (Cornell University, 1979-10)
    This paper presents an on-line 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 on-line ...
  • Ensuring Consistency in a Distributed Database System by Use of Distributed Semaphores 

    Schneider, Fred B. (Cornell University, 1979-09)
    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, 1979-09)
    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, 1979-09)
    For a complexity measure $\kappa$, a set is $\kappa$-infinite if it contains a $\kappa$-decidable infinite subset. For a time-based $\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, 1979-08)
  • The Complexity of Parallel Computations 

    Wyllie, James C. (Cornell University, 1979-08)
    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, 1979-07)
    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 Time-Space Tradeoff for In-Place Array Permutation 

    Melville, Robert C. (Cornell University, 1979-07)

View more


RSS Feeds