A pattern alpha (i.e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of alpha by terminal words. The respective matching problem, i.e., deciding wheth...
详细信息
A pattern alpha (i.e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of alpha by terminal words. The respective matching problem, i.e., deciding whether or not a given pattern matches a given word, is generally np-complete, but can be solved in polynomial-time for restricted classes of patterns. We present efficient algorithms for the matching problem with respect to patterns with a bounded number of repeated variables and patterns with a structural restriction on the order of variables. Furthermore, we show that it is np-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors. As an immediate consequence of this hardness result, the injective version (i.e., different variables are replaced by different words) of the matching problem is np-complete even for very restricted classes of patterns.
A pattern (i. e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by terminal words;deciding this is np-complete. We present efficient algorithms(1) that s...
详细信息
ISBN:
(纸本)9783939897781
A pattern (i. e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by terminal words;deciding this is np-complete. We present efficient algorithms(1) that solve this problem for restricted classes of patterns. Furthermore, we show that it is np-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors;this shows that the injective version (i. e., different variables are replaced by different words) of the above matching problem is np-complete even for very restricted cases.
暂无评论