Browsing LCS Publications by Title
Now showing items 586-605 of 1163
-
K+1 Heads are Better Than K
(1976-09)There are languages which can be recognized by a deterministic (k+1)-headed one-way finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, ... -
Knowledge and Common Knowledge in a Byzantine Environment: Crash failures
(1986-07)By analyzing the states of knowledge that the processors attain in an unreliable system of a simple type, we capture some of the basic underlying structure of such systems. In particular, we study what facts become common ... -
Knowledge Representation for Supporting Decision Model Formulation in Medicine
(1991-06)Clinical decision making involves a large, complex, and ever-changing body of knowledge. Characterizing such knowledge illuminates the representational and computational requirements for automated clinical decision analysis. -
KOLA: Knowledge Organization Language
(1988-10)The focus of this research is on a representation of knowledge that captures the structure of a domain into the computational model for efficient retrieval and reasoning. With this desideratum in mind, a concept-based ... -
Lambda Calculus Models of Programming Languages
(1968-12)Two aspects of programming languages, recursive definitions and type declarations are analyzed in detail. Church's -calculus is used as a model of a programming language for purposes of the analysis. The main result on ... -
A Lattice-structured Proof Technique Applied to a Minimum Spanning Tree Algorithm
(1988-06)Higly-optimized concurrent algorithms are often hard to prove correct because they have no natural decomposition into separately provable parts. This paper presents a proof technique for the modular verification of such ... -
A Layered Virtual Memory Manager
(1977-05)This thesis presents a specification for the Multics virtual memory manager. The virtual memory manager is that part of the operating system which coordinates the usage of physical memory and which manages the bindings ... -
Layouts for the Shuffle-exchange Graph and Lower Bound Techniques for VLSI
(1982-08)The thesis is divided into two parts. In the first part, we describe and analyze several new VLSI layouts for the shuffle-exchange graph. These include:1) an asymptotically optimal, (N /log N)-area layout for the ... -
Layouts for the Suffle-Exchange Graph Based on the Complex Plane Diagram
(1982-06)The shuffule-exchange graph is one of the best structures known for parallel computation. Among other things, a shuffle-exchange computer can be used to compute discrete. Fourier transforms, multiply matrices, evaluate ... -
Lazy Reference Counting for Transactional Storage Systems
(1997-10)HAC is a novel technique for managing the direct the client cache in a distributed, persistent object storage system. In a companion paper, we showed that it outperforms other techniques across a wide range of cache sizes ... -
Lazy Replication: Exploiting the Semantics of Distributed Services
(1990-07)To provide high availability for services such as mail or bulletin boards, data must be replicated. One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all ... -
Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs
(1991-06)Many parallel algorithms are naturally expressed at a fine level of granularity, often finer than MIMD parallel system can exploit efficiently. Most builders of parallel systems have looked to either the programmer or a ... -
Light Traps
(1996-10)In the February 1992 issue of the American Mathematical Monthly, J. E. Connett [1] asked whether it is possible to construct a 'light trap': a reflective-sided container with the property that a beam of light, shone into ... -
Limitless Directories: A Scalable Cache Coherence Scheme
(1991-06)Caches enhance the performance of multiprocessors by reducing network traffic and average memory access latency. However, cache-based systems must address the problem of cache coherence. We propose the LimitLESS directory ... -
Linearizable Counting Networks
(1991-11)The counting problem requires n asynchronous processors to assign themselves successive values. A solution is linearizable if the order of the values assigned reflects the real-time order in which they were requested. ... -
Liveness in Timed and Untimed Systems
(1993-12)When proving the correctness of algorithms in distributed systems, one generally considers safety conditions and liveness conditions. The Input /Output (I/)0 automaton model and its timed version have used successfully, ...
