Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334255 | Theoretical Computer Science | 2005 | 11 Pages |
Abstract
We address the following issue: given a word wâA* and a set of n nonempty words X, how does one determine efficiently whether wâX* or not? We discuss several methods including an O(rÃ|w|+|X|) algorithm for this problem where r⩽n is the length of a longest suffix chain of X and |X| is the sum of the lengths of words in X. We also consider the more general problem of providing all the decompositions of w in words of X.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Julien Clément, Jean-Pierre Duval, Giovanna Guaiana, Dominique Perrin, Giuseppina Rindone,