𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A practical algorithm to find the best subsequence patterns

✍ Scribed by Masahiro Hirao; Hiromasa Hoshino; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
171 KB
Volume
292
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

An Algorithm for Finding the K-Best Allo
An Algorithm for Finding the K-Best Allocations of a Tree Structured Program
✍ A. Billionnet; S. Elloumi πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 592 KB

We consider the problem of allocating \(n\) tasks of a distributed program to \(m\) processors of a distributed system in order to minimize total communication and processing costs. If the intertask communication can be represented by a tree and if the communication costs are uniform, it is known th

A Self-Stabilizing Distributed Algorithm
A Self-Stabilizing Distributed Algorithm to Find the Median of a Tree Graph
✍ Gheorghe Antonoiu; Pradip K. Srimani πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 231 KB

We propose a self-stabilizing algorithm (protocol) for computing the median in a given tree graph. We show the correctness of the proposed algorithm by using a new technique involving induction.