DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2015.302

Pattern Matching with Variables: Fast Algorithms and New Hardness Results

Authors: Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

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\footnote{The computational model we use is the standard unit-cost RAM with logarithmic word size. Also, all logarithms appearing in our time complexity evaluations are in base 2.} 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.

Cite as

Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid. Pattern Matching with Variables: Fast Algorithms and New Hardness Results. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 302-315, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fernau_et_al:LIPIcs.STACS.2015.302,
  author =	{Fernau, Henning and Manea, Florin and Mercas, Robert and Schmid, Markus L.},
  title =	{{Pattern Matching with Variables: Fast Algorithms and New Hardness Results}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{302--315},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.302},
  URN =		{urn:nbn:de:0030-drops-49220},
  doi =		{10.4230/LIPIcs.STACS.2015.302},
  annote =	{Keywords: combinatorial pattern matching, combinatorics on words, patterns with variables, \$\{cal NP\}\$-complete string problems}
}

Document

DOI: 10.4230/LIPIcs.STACS.2013.257

Finding Pseudo-repetitions

Authors: Pawel Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka, and Catalin Tiseanu

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract

Pseudo-repetitions are a natural generalization of the classical notion of repetitions in sequences. We solve fundamental algorithmic questions on pseudo-repetitions by application of insightful combinatorial results on words. More precisely, we efficiently decide whether a word is a pseudo-repetition and find all the pseudo-repetitive factors of a word.

Cite as

Pawel Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka, and Catalin Tiseanu. Finding Pseudo-repetitions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 257-268, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.STACS.2013.257,
  author =	{Gawrychowski, Pawel and Manea, Florin and Mercas, Robert and Nowotka, Dirk and Tiseanu, Catalin},
  title =	{{Finding Pseudo-repetitions}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{257--268},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.257},
  URN =		{urn:nbn:de:0030-drops-39394},
  doi =		{10.4230/LIPIcs.STACS.2013.257},
  annote =	{Keywords: Stringology, Pattern matching, Repetition, Pseudo-repetition}
}

Search Results

Documents authored by Mercas, Robert

Pattern Matching with Variables: Fast Algorithms and New Hardness Results

Abstract

Cite as

Finding Pseudo-repetitions

Abstract

Cite as

Thanks for your feedback!

Could not send message