×
Masek, William J.; Paterson, Michael S.

A faster algorithm computing string edit distances. (English) Zbl 0436.68044

J. Comput. Syst. Sci. 20, 18-31 (1980).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0436.68044

Cited in 1 Review
Cited in 115 Documents

MSC:

68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity

Keywords:

edit distance; character strings; longest common subsequence
PDF BibTeX XML Cite
\textit{W. J. Masek} and \textit{M. S. Paterson}, J. Comput. Syst. Sci. 20, 18--31 (1980; Zbl 0436.68044)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Aho, A.V.; Hirschberg, D.S.; Ullman, J.D., Bounds on the complexity of the longest common subsequence problem, J. assoc: comput. Mach., 23, No. 1, 1-12, (1976) · Zbl 0316.68027
[2] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[3] Arlazarov, V.L.; Dinic, E.A.; Kronrod, M.A.; Faradzev, I.A., On economic construction of the, transitive closure of a directed graph, Dokl. akad. nauk SSSR, Soviet math. dokl., 11, No.5, 1209-1210, (1970), [in Russian]. English translation · Zbl 0214.23601
[4] Hirschberg, D.S., A linear space algorithm for computing maximal common subsequences, Cacm, 18, No. 6, 341-343, (1975) · Zbl 0301.68042
[5] Hopcroft, J.E.; Paul, W.J.; Valiant, L.G., On time versus space and other related problems, (), 57-64
[6] Lowbance, R.; Wagner, R.A., An extension of the string to string correction problem, J. assoc. comput. Mach., 22, No. 2, 177-183, (1975) · Zbl 0301.68028
[7] Wagner, R.A.; Fischer, M.J., The string to string correction problem, J. assoc. comput. Mach., 21, No. 1, 168-183, (1974) · Zbl 0278.68032
[8] Wong, C.K.; Chandra, A.K., Bounds for the string editing problem, J. assoc. comput. Mach., 23, No. 1, 13-16, (1976) · Zbl 0316.68019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.