Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 316-335 of 492
-
On the Mathematics of Virus Shell Assembly
(1994-07)A local rule theory is developed which shows that the self-assembly of icosahedral virus shells may depend on only the lower-level interactions of a protein subunit with its neighbors, i.e. local rules, rather than on ... -
On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.)
(1984-03)We consider the following problem: Let s be a n-bit string with m ones and n-m zeros. Denote by CEt(s) the number of pairs, of equal bits which are within distance t apart, in the string s. What is the minimum value of ... -
On the Redundancy Achieved by Huffman Codes
(1995-09)It has been recently proved that the redundancy r of any discrete memoryless source satisfies r < 1 -H(pn), where pn is the least likely source letter probability. This bound is achieved only by sources consisting of two ... -
On the Security of the Merkle-Hellman Cryptographic Scheme
(1978-12)In this paper we show that a simplified version of the Merkel-Hellman public-key cryptographic system is breakable. While their full-fledged system seems to be resistant to the cryptanalytic attack we propose, this result ... -
On the Sequential Nature of Unification
(1984-03)The problem of unification of terms is log-space complete for P. In deriving this lower bound no use is made of the potentially concise representation of terms by directed acyclic graphs. In addition, the problem remains ... -
On the Worst-case Behavior of String-searching Algorithms
(1976-04)Any algorithm for finding a pattern of length k in a string of length n must examine at least n-k+1 of the characters of the string in the worst case. By considering the pattern 00…0, we prove that this is the best possible ... -
On Triangulations of a Set of Points in the Plane
(1977-07)A set, V, of points in the plane is triangulated by a subset, T, of the straight line segments whose enpoints are in V, if T is a maximal subset such that the line segments in T intersect only at their endpoints. The weight ... -
On-line Scheduling of Parallel Machines
(1990-11)We study the problem of scheduling jobs on parallel machines in an on-line fashion, where the processing requirement of a job is not known until the job is completed. Despite this lack of knowledge of the future, we wish ... -
Online Tracking of Mobile Users
(1989-08)This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept of regional matching, ... -
Operational Semantics of a Data Flow Language
(1978-12)A data flow machine achieves high performance by the concurrent execution of machine code consisting of data flow graphs which explicitly represent the data dependencies among program instructions. This thesis presents the ... -
An Operator Embedding Theorem for Complexity Classes of Recursive Functions
(1973-05)Let F (t) be the set of functions computable by some machine using no more than t(x) machine steps on all but finitely many arguments x. If we order the - classes under set inclusion as t varies over the recursive functions, ... -
Opportunistic Log: Efficient Installation Reads in a Reliable Object Server
(1994-04)In a distributed storage system, client caches managed on the basis of small granularity objects can provide better memory utilization then page-based caches. However, object servers, unlike page servers, must perform ... -
Optimal Arrangement of Keys in a Hash Table
(1976-07)When open addressing is used to resolve collisions in a hash table, a given set of keys may be arranged in many ways; typically this depends on the order in which the keys are inserted. We show that arrangements minimizing ... -
Optimal Clock Synchronization Under Different Delay Assumptions
(1994-04)The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family ... -
Optimal Distributed Algorithms for Sorting and Ranking
(1984-05)We study the problems of sorting and ranking n processors that have initial values - not necessarily distinct - in a distrubuted system. Sorting means that the initial values have to move around in the network and be ... -
Optimal Placement for River Routing
(1981-10)Programs for integrated circuit layout typically have two phases: placement and routing. The router should produce as efficient a layout as possible, but of course the quality of the routhing depends heavily on the quality ... -
An Optimality Theory of Concurrency Control for Databases
(1980-11)A concurrency control mechanism (or a scheduler) is the component of a database system that safeguards the consistency of the database in the presence of interleaved accesses and update requests. We formally show that the ... -
Optimizing Synchronous Systems
(1982-03)The complexity of integrated-circuit chips produced today makes it feasible to build inexpensive, special-purpose subsystems that rapidly solve sophisticated problems on behalf of a general-purpose host computer. This paper ... -
An Overview of OWL, A Language for Knowledge Representation
(1977-06)We describe the motivation and overall organization of the OWL language for knowledge representation. OWL consists of a memory of concepts in terms of which all English phrases and all knowledge of an application domain ...
