Pattern matching with variables: A multivariate complexity analysis

A pattern α, i. e. , a string that contains variables and terminals, matches a terminal word w if w can be obtained by uniformly substituting the variables of α by terminal words. Deciding whether a given terminal word matches a given pattern is NP-complete and this holds for several natural variants of the problem that result from whether or not variables can be erased, whether or not the patterns are required to be terminal-free or whether or not the mapping of variables to terminal words must be injective. We consider numerous parameters of this problem (i. e. , number of variables, length of w, length of the words substituted for variables, number of occurrences per variable, cardinality of the terminal alphabet) and for all possible combinations of the parameters (and variants described above), we answer the question whether or not the problem is still NP-complete if these parameters are bounded by constants.

Authors

• Henning Fernau
• Markus L. Schmid

Keywords

• Parameterised pattern matching
• Function matching
• NP-completeness
• Membership problem for pattern languages
• Morphisms