Journal of the ACM Bibliography

Categories and Subject Descriptors: E.4 [Coding and Information Theory] -- data compaction and compression; F.1.3 [Computation by Abstract Devices]: Complexity Classes -- reducibility and completeness; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- pattern matching

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Textual substitution, macro expansion, dictionary, NP-completeness

Selected papers that cite this one

• Timothy C. Bell and Ian H. Witten. The relationship between greedy parsing and symbolwise text compression. Journal of the ACM, 41(4):708-724, July 1994.

• Paolo Ferragina, Roberto Grossi, and Manuela Montangero. On updating suffix tree labels. Theoretical Computer Science, 201(1-2):249-262, 6 July 1998. Note.

• Shang-Hua Teng and Frances Yao. Approximating shortest superstrings. In 34th Annual Symposium on Foundations of Computer Science, pages 158-165, Palo Alto, California, 3-5 November 1993. IEEE.

• Shang-Hua Teng and Frances F. Yao. Approximating shortest superstrings. SIAM Journal on Computing, 26(2):410-417, April 1997.

Selected references

• Robert S. Boyer and J. Strother Moore. A fast string searching algorithm. Communications of the ACM, 20(10):762-772, October 1977. See also \cite{Knuth:1977:FPM} and \cite{Sunday:1990:VFS}.

• Stephen A. Cook. The complexity of theorem-proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 151-158, Shaker Heights, Ohio, 3-5 1971 1971.

• Bruce Hahn. A new technique for compression and storage of data. Communications of the ACM, 17(8):434-436, August 1974.

• B. A. Marron and P. A. D. de Maine. Automatic data compression. Communications of the ACM, 10(11):711-715, November 1967. Also published in/as: File Organization, Siwerts and Zeitlinge (Amsterdam), 1969.

• Edward M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23(2):262-272, April 1976.

• Michael Rodeh, Vaughan R. Pratt, and Shimon Even. Linear algorithm for data compression via string matching. Journal of the ACM, 28(1):16-24, January 1981.

• Frank Rubin. Experiments in text file compression. Communications of the ACM, 19(11):617-623, November 1976.

• James A. Storer and Thomas G. Szymanski. The macro model for data compression (extended abstract). In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, pages 30-39, San Diego, California, 1-3 May 1978.

• Robert A. Wagner. Common phrases and minimum-space text storage. Communications of the ACM, 16(3):148-152, March 1973.

• Peter Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on Switching and Automata Theory, pages 1-11, The University of Iowa, 15-17 October 1973. IEEE.

Shortcuts: