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 a by terminal words. The respective matching problem, i. e., deciding whether...
详细信息
ISBN:
(数字)9783030287962
ISBN:
(纸本)9783030287962;9783030287955
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 a 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 classes of patterns with restricted structure. In this paper we overview a series of recent results related to efficient matching for patterns with variables, as well as a series of extensions of this problem.
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.
Given a pattern p = s(1)x(1)s(2)x(2) center dot center dot center dot s(r-1)x(r-1)s(r) such that x(1), x(2),..., x(r-1) is an element of {x, (x) over left arrow>}, where (x) over left arrow is a variable and. x its...
详细信息
ISBN:
(纸本)9783319674285;9783319674278
Given a pattern p = s(1)x(1)s(2)x(2) center dot center dot center dot s(r-1)x(r-1)s(r) such that x(1), x(2),..., x(r-1) is an element of {x, (x) over left arrow>}, where (x) over left arrow is a variable and. x its reversal, and s(1), s(2),..., s(r) are strings that contain no variables, we describe an algorithm that constructs in O(rn) time a compact representation of all P instances of p in an input string of length n over a polynomially bounded integer alphabet, so that one can report those instances in O(P) time.
暂无评论