Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 1-20 of 492
-
Acquisition of a Large Pose-Mosaic Dataset
(1998-01)We describe the generation of a large pose-mosaic dataset: a collection of several thousand digital images, grouped by spatial position into spherical mosaics, each annotated with estimates of the acquiring camera's 6 DOF ... -
Action Transducers and Timed Automata
(1992-11)The timed automaton model of [29, 30] is a general model for timing-based systems. A notion of timed action transducer is here defined as an automata-theoretic way of representing operations on timed automata. It is shown ... -
Addressing Partitioned Arrays in Distributed Memory Multiprocessors - the Software Virtual Memory Approach
(1994-12)Harnessing the full performance potential of cache-coherent distributed shared memory multiprocessors without inordinate user effort requires a compilation technology that can automatically manage multiple levels of memory ... -
Algebraic Dependencies
(1981-02)We propose a new kind of data dependencies called algebraic dependencies, which generalize all previous known kinds. We give a complete axiomatization of algebraic dependencies in terms of simple algebraic rewriting rules. ... -
Algorithms for Modeling and Measuring Proteins
(1995-06)In this paper we investigate efficient algorithms for computing the volume and surface area of protein molecules are modeled by sets of overlapping spheres in R 3. We summarize and critique three papers in the field, and ... -
Algorithms for Scheduling Tasks on Unrelated Processors
(1979-06)Several algorithms are presented for the nonpreemptive assignment of n independent tasks to m unrelated processors. One algorithm requires polynomial time in n and m, and is at most 2√m times worse than optimal in the worst ... -
An Analysis of Computer Decentralization
(1977-10)This thesis is concerned with the recent trend toward decentralization of the computer facility. We conjecture that there are strong forces in many organizations leading towards decentralization, which have been held in ... -
An Analysis of Preemptive Multiprocessor Job Scheduling
(1978-09)The preemptive scheduling of a partially ordered set of tasks is studied. A class of scheduling heuristics is introduced, and the performance of schedules in this class is analyzed with respect to the least finishing time ... -
An Analysis of Rabin's Randomized Mutual Exclusion Algorithm: Preliminary Report
(1991-12)In 1982, Michael Rabin published a randomized distributed algorithm implementing mutual exclusion for n processes using a read-modify-write primitive on a shared variable with O(log n) values. He claimed that this algorithm ... -
An Analysis of the Solovay and Strassen Test for Primality
(1978-07)In this paper we will analyze the performace of the Solovay and Strasses probabilistic primality testing algorithm. We will show that iterating Solovay and Strassen's algorithm r times using independent random numbers at ... -
Analyzing Multiprocessor Cache Behavior Through Data Reference Modeling
(1993-02)This paper develops a data reference modeling technique to estimate with high accuracy the cache miss ratio in cache-coherent multiprocessors. The technique involves analyzing the dynamic data referencing behavior of ... -
Ancillary Reports: Kernel Design Project
(1977-06) -
An Application of Digital Broadcast Communication to Large Scale Information Systems
(1986-04)A new type of information system is described that combines personal computers, broadcast data communication, and bidirectional communication. The system is designed to use broadcast communciation whenever possible to ... -
Application of Minimal Perfect Hashing in Main Memory Indexing
(1994-05)With the rapid decrease in the cost of random access memory (RAM), it will soon become economically feasible to place full-text indexes of a library in main memory. One essential component of the indexing system is a ... -
An Application of Number Theory to the Organization of Raster Graphics Memory
(1984-04)A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ... -
Applications of Modal Logic to Programming
(1978-12)The modal logician's notion of possible world and the computer scientist's notion of state of a machine provide a point of commonality which can form the foundation of a logic of action. Extending ordinary modal logic with ... -
Approximating the Minimum-cost Maximum Flow is P-Complete
(1992-06)We show that it is impossible, in NC, to approximate the value of the minimum-cost maximum flow unless P = NC. -
An Approximation Algorithm for Manhattan Routing
(1983-02)Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, we identify a second important measure of difficulty, which we call flux. We show that flux, like density, is a ...
