Opening book details…
Can I read A Practical Algorithm to Find the Best Subsequence Patterns on EtoBox?
A Practical Algorithm to Find the Best Subsequence Patterns by Masahiro Hirao; Hiromasa Hoshino; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa is a Computer Science article available to read on EtoBox.
What is A Practical Algorithm to Find the Best Subsequence Patterns about?
Given two sets of strings, consider the problem to ÿnd a subsequence that is common to one set but never appears in the other set. We regard it to ÿnd a subsequence pattern which separates these two sets. The problem is known to be NP-complete. We naturally generalize it to an optimization problem, where we try to ÿnd a subsequence pattern which maximally separates these two sets. We provide a practical algorithm to solve it exactly. Our algorithm uses two pruning heuristics based on the properties of subsequence languages, and utilizes the data structure called subsequence automata. We report some experimental results, which show these heuristics and the data structure contribute to reduce the search time.
Who reads A Practical Algorithm to Find the Best Subsequence Patterns?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Masahiro Hirao; Hiromasa Hoshino; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)
- Published
- 2003
- Language
- EN
- Field
- Computer Science (Physical Sciences)