TY - GEN
T1 - A practical algorithm to find the best subsequence patterns
AU - Hirao, Masahiro
AU - Hoshino, Hiromasa
AU - Shinohara, Ayumi
AU - Takeda, Masayuki
AU - Arikawa, Setsuo
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. We generalize the problem to an optimization problem, and give a practical algorithm to solve it exactly. Our algorithm uses pruning heuristic and subsequence automata, and can find the best subsequence. We show some experiments, that convinced us the approach is quite promising.
AB - Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. We generalize the problem to an optimization problem, and give a practical algorithm to solve it exactly. Our algorithm uses pruning heuristic and subsequence automata, and can find the best subsequence. We show some experiments, that convinced us the approach is quite promising.
UR - http://www.scopus.com/inward/record.url?scp=84974712011&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84974712011&partnerID=8YFLogxK
U2 - 10.1007/3-540-44418-1_12
DO - 10.1007/3-540-44418-1_12
M3 - Conference contribution
AN - SCOPUS:84974712011
SN - 9783540413523
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 141
EP - 153
BT - Discovery Science - 3rd International Conference, DS 2000, Proceedings
A2 - Arikawa, Setsuo
A2 - Morishita, Shinichi
PB - Springer Verlag
T2 - 3rd International Conference on Discovery Science, DS 2000
Y2 - 4 December 2000 through 6 December 2000
ER -