September 1976 - Vol. 19 No. 9
Features
Analysis of an algorithm for real time garbage collection
A real time garbage collection system avoids suspending the operations of a list processor for the long times that garbage collection normally requires by performing…
New upper bounds for selection
The worst-case, minimum number of comparisons complexity Vi(n) of the i-th selection problem is considered. A new upper bound for Vi(n) improves the bound given by the…
The nodes of a weighted derivation tree are associated with weighting functions over the vocabulary of a context-free grammar. An algorithm is presented for constructing…
Recursion analysis for compiler optimization
A relatively simple method for the detection of recursive use of procedures is presented for use in compiler optimization. Implementation considerations are discussed,…
Efficient generation of the binary reflected gray code and its applications
Algorithms are presented to generate the n-bit binary reflected Gray code and codewords of fixed weight in that code. Both algorithms are efficient in that the time…
An efficient, incremental, automatic garbage collector
This paper describes a new way of solving the storage reclamation problem for a system such as Lisp that allocates storage automatically from a heap, and does not require…
Faster retrieval from context trees
Context trees provide a convenient way of storing data which is to be viewed as a hierarchy of contexts. This note presents an algorithm which improves on previous…