FMMS_2015_TOCT.pdf (900.21 kB)
Download file

Pattern matching with variables: Efficient algorithms and complexity results

Download (900.21 kB)
journal contribution
posted on 29.10.2019, 16:45 by Henning Fernau, Florin Manea, Robert MercasRobert Mercas, Markus Schmid
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.

Funding

DFG grant MA 5725/1-2 (project number 218587403)

History

School

  • Science

Department

  • Computer Science

Published in

ACM Transactions on Computation Theory

Volume

12

Issue

1

Publisher

Association for Computing Machinery

Version

AM (Accepted Manuscript)

Rights holder

© Association for Computing Machinery

Publisher statement

© ACM 2020. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computation Theory, https://doi.org/10.1145/3369935.

Acceptance date

21/10/2019

Publication date

2020-02-11

Copyright date

2020

Notes

This is the author's version of the work created using a standard ACM template using dummy details, i.e., journal title, vol, issue, article number, publication, doi. The citation on the template should be ignored. The correct citation details are in the record metadata.

ISSN

1942-3454

eISSN

1942-3462

Language

en

Depositor

Dr Robert Mercas. Deposit date: 28 October 2019

Article number

6