Key points are not available for this paper at this time.
The file transmission problem is to determine the best way to send a file A (assumed to be a linear string over a finite alphabet) from one computer to another via a transmission line, assuming that the receiving computer has access to another file B called the base file. In addition to sending the characters of A directly, we allow the transmission of a copy command which directs the receiving computer to append a specified, but variable length, substring of characters taken from the base file to the end of the file under construction. The cost of transmission is taken as the sum of the number of characters directly sent and K times the number of copy commands. An optimal derivation of A is a minimum-cost sequence of characters and copy commands which allow the receiving computer to construct the file A. We present an algorithm for obtaining an optimal derivation. This algorithm is itself optimal in that both its run time and storage requirements are linear functions of the lengths of A and B.
Peter Weiner (Mon,) studied this question.