Loading…
Pattern matching with variables: Efficient algorithms and complexity results
A pattern α (i. e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of α 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 solv...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Default Article |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/2134/10059554.v1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1818167742347345920 |
|---|---|
| author | Henning Fernau Florin Manea Robert Mercas Markus Schmid |
| author_facet | Henning Fernau Florin Manea Robert Mercas Markus Schmid |
| author_sort | Henning Fernau (7168292) |
| collection | Figshare |
| description | A pattern α (i. e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of α 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 clases of patterns. |
| format | Default Article |
| id | rr-article-10059554 |
| institution | Loughborough University |
| publishDate | 2020 |
| record_format | Figshare |
| spelling | rr-article-100595542020-02-11T00:00:00Z Pattern matching with variables: Efficient algorithms and complexity results Henning Fernau (7168292) Florin Manea (7168022) Robert Mercas (2835212) Markus Schmid (59491) Theory of computation not elsewhere classified Combinatorial pattern matching Combinatorics on words Patterns with variables NP-complete string problems Computation Theory and Mathematics A pattern α (i. e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of α 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 clases of patterns. 2020-02-11T00:00:00Z Text Journal contribution 2134/10059554.v1 https://figshare.com/articles/journal_contribution/Pattern_matching_with_variables_Efficient_algorithms_and_complexity_results/10059554 All Rights Reserved |
| spellingShingle | Theory of computation not elsewhere classified Combinatorial pattern matching Combinatorics on words Patterns with variables NP-complete string problems Computation Theory and Mathematics Henning Fernau Florin Manea Robert Mercas Markus Schmid Pattern matching with variables: Efficient algorithms and complexity results |
| title | Pattern matching with variables: Efficient algorithms and complexity results |
| title_full | Pattern matching with variables: Efficient algorithms and complexity results |
| title_fullStr | Pattern matching with variables: Efficient algorithms and complexity results |
| title_full_unstemmed | Pattern matching with variables: Efficient algorithms and complexity results |
| title_short | Pattern matching with variables: Efficient algorithms and complexity results |
| title_sort | pattern matching with variables: efficient algorithms and complexity results |
| topic | Theory of computation not elsewhere classified Combinatorial pattern matching Combinatorics on words Patterns with variables NP-complete string problems Computation Theory and Mathematics |
| url | https://hdl.handle.net/2134/10059554.v1 |