George E. Collins
Abstract
An important property of the Newell Shaw-Simon scheme for computer storage of lists is that data having multiple occurrences need not be stored at more than one place in the computer. That is, lists may be “overlapped.” Unfortunately, overlapping poses a problem for subsequent erasure. Given a list that is no longer needed, it is desired to erase just those parts that do not overlap other lists. In LISP, McCarthy employs an elegant but inefficient solution to the problem. The present paper describes a general method which enables efficient erasure. The method employs interspersed reference counts to describe the extent of the overlapping.
- 1 COLLINS, G. E. Tarski's decision method for elementary algebra. Proc. of the Summer Institute of Symbolic Logic, 1957, pp. 64-70.Google Scholar
- 2 GELERNTER, H.; HANSEN, J. R.; AND GERBERICH, C. L. A Fortran-compiled list processing language. J. Assoc. Comput. Mach. 7 (1960), 87-101. Google ScholarDigital Library
- 3 McCARTHY, J. Recursive functions of symbolic expressions and their computation by machine, Part I. Commun. ACM 3 (1960), 184-195. Google ScholarDigital Library
- 4 NEWELL, A.; SHAW, J. C.; AND SIMON, H. A. Empirical ex plorations of the logic theory machine. Proc. of the 1957 Western Joint Computer Conference, pp. 218-230.Google Scholar
- 5 TARSKI, A. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.Google Scholar
Recommendations
Burst erasure correcting LDPC codes
In this paper low-density parity-check (LDPC) codes are designed for burst erasure channels. Firstly, lower bounds for the maximum length erasure burst that can always be corrected with message-passing decoding are derived as a function of the parity-...
Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets
This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of ...
Turbo Codes in Binary Erasure Channel
In this correspondence, the stopping set of turbo codes with iterative decoding in the binary erasure channel is defined. Block and bit erasure probabilities of turbo codes are studied by using the stopping set analysis. It is found that block and bit ...
Comments