Browsing LCS Publications by Title

Now showing items 1002-1021 of 1163

    • The Space Complexity of Two Pebbles Games on Trees 

      Loui, Michael C. (1979-05)
      In the standard pebble game the number of pebbles required to pebble the root of a tree can be computed in time linearly proportional to the number of nodes. For the black/white pebble game the number of pebbles necessary ...

    • Space-Bounded Simulation of Multitape Turing Machines 

      Adleman, Leonard M.; Loui, Michael C. (1980-01)
      A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: every deterministic multitape Turing machine of time complexity T(n) can be simulated by a deterministic Turing machine of space complexity T(n)/log ...

    • A Space-efficient Algorithm for Finding the Connected Components of Rectangles in the Plane 

      Leiserson, Charles E.; Phillips, Cynthia A. (1987-02)
      We present an algorithm for determining the connectivity of a set of N rectangles in the plane, a problem central to avoiding aliasing in VLSI design rule checkers. Previous algorithms for this problem either worked slowly ...

    • A Spacially and Temporally Coherent Object Space Visibility Algorithm 

      Coorg, Satyan; Teller, Seth (1996-02)
      Efficiently identifying polygons that are visible from a changing synthetic viewpoint is an important problem in computer graphics. In many complex geometric models, most parts of the model are invisible from the instantaneous ...

    • Specification and Implementation of Atomic Data Types 

      Weihl, William Edward (1984-03)
      Maintaining the consistency of long-lived, on-line data is a difficult task, particularly in a distributed system. This dissertation focuses on atomicity as a fundamental organizational concept for such systems. It ...

    • Specification and Verification of Real-team Constraints in Coarse-grain Dataflow 

      Henry, Dana S. (1991-05)
      We present a method for verifying real-time constraints in a distributed, coarse-grain dataflow environment starting with a program which has already been allocated onto a machine. The user specifies the timing of each ...

    • The Specification of Code Generation Algorithms 

      Terman, Christopher J. (1978-04)
      This thesis addresses the problem of automatically constructing the code generation phrase of a compiler from a specification of the source language and target machine. A framework for such a specification is presented ...

    • Specifications and Verification Techniques for Parallel Programs Based on Message Passing Semantics 

      Yonezawa, Akinori (1978-01)
      This thesis presents formal specification and verification techniques for both serial and parallel programs written in SIMULA-like object oriented languages. These techniques are based on the notion of states of individual ...

    • Specifying and Using a Partitionable Group Communication Service* 

      Fekete, Alan; Lynch, Nancy A.; Shvartsman, Alexander A. (1997-08)
      A new, simple formal specification is presented for a partitionable view-oriented group communication service. The specification consists of a state machine to express safety requirements and a timed trace property to ...

    • The Spectral Norm of Finite Functions 

      Bellare, Mihir (1991-02)
      In many recent results in learning and computational complexity theory which rely on Fourier analysis, the spectral norm plays a key role. An understanding of this quantity would appear to be useful in both gauging and ...

    • Speech Perception Using Real-Time Phoneme Detection: The BeBe System 

      Sweeny, Latanya; Thompson, Patrick (1998-04)
      We define a new approach to speech recognition based on auditory perception and modeled after the human brain's tendency to automatically categorize speech sounds [House 1962; Liberman 1957]. As background, today's speech ...

    • The Static Single Information Form 

      Ananian, C. Scott (1999-09)
      The Static Single Information (SSI) form is a compiler intermediate representation that allows efficient sparse implementations of predicated analysis and backward dataflow algorithms. It possesses several attractive ...

    • A Statistical Approach to Language Modelling for the ATIS Problem 

      Koppelman, Joshua D. (1995-02)

    • Statistical Trajectory Models for Phonetic Recognition 

      Goldenthal, William David (1994-08)
      The main goal of this work is to develop an alternative methodology for acoustic-phonetic modelling of speech sounds. The approach utilizes a segment-based framework to capture the dynamical behavior and statistical ...

    • Steam-oriented Computation in Recursive Data Flow Schemas 

      Weng, Kung-Song (1975-10)
      In this thesis we present a parallel programming language based on a parallel computation model known as data flow schemas. Syntactically, the language resembles programming languages such as Algol 60, but does not have ...

    • Stochastic Analysis of Qualitative Dynamics 

      Doyle, Jon; Sacks, Elisha P. (1989-12)

    • Storage and Access Costs for Implementations of Variable - Length lists 

      Brown, Donna Jean (1979-04)
      Consider a machine with a cellular memory used to store a list X , where X is a finite alphabet and i N. We investigate the machine representation of such a list and the implementation of common list operations such as ...

    • Storage Hierarchy Systems 

      Madnick, Stuart E. (1973-04)
      The relationship between page size, program behavior, and page fetch frequency in storage hierarchy systems is formalized and analyzed. It is proven that there exist cyclic program reference patterns that can cause page ...

    • Strategy Selection in Medical Diagnosis 

      Miller, Peter B. (1975-09)
      The recorded, verbal problem-solving behavior of doctors performing the diagnostic task of taking a present illness was analyzed in this research. The goal of the analysis was to discover that data-acquisition strategies ...

    • Stream Algorithms and Architecture 

      Henry, Hoffman; Strumpen, Volker; Agarwal, Anant (2003-03)
      Wire-exposed, programmable microarchitectures including Trips [11]], Smart Memories [8], and Raw [13] offer an opportunity to schedule instruction execution and data movement explicitly. This paper proposes stream algorithms, ...