String editing on a one-way linear array of finite-state machines

Author

Ibarra, Oscar H. ; Jiang, Tao ; Wang, Hui

Author_Institution

Dept. of Comput. Sci., California Univ., Santa Barbara, CA, USA

Volume

41

Issue

1

fYear

1992

fDate

1/1/1992 12:00:00 AM

Firstpage

112

Lastpage

118

Abstract

The authors give an efficient parallel algorithm for the string edit problem. The model of computation is a one-way linear array of identical finite-state machines (nodes). The data movement in the array is one-way, from left to right. For inputs of length n, the array uses n nodes. The algorithm can produce the actual minimum-cost edit sequence in linear time. The previous parallel algorithm for this problem runs in O(n) time on a one-way two-dimensional array of finite-state machines using n ² nodes. The best serial (RAM) algorithm for the problem takes O(n²/log n) time and space. Applications to other problems such as the longest common subsequence and approximate pattern matching are discussed

Keywords

finite automata; parallel algorithms; RAM; approximate pattern matching; finite-state machines; linear time; longest common subsequence; minimum-cost edit sequence; model of computation; one-way linear array; one-way two-dimensional array; parallel algorithm; string editing; Computational modeling; Computer science; Concurrent computing; Costs; Iterative algorithms; Linear programming; Parallel algorithms; Parallel programming; Pattern matching; Read-write memory;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.123389

Filename

123389