License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2012.272
URN: urn:nbn:de:0030-drops-34981
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3498/
Go to the corresponding LIPIcs Volume Portal

Schmidt-Schauß, Manfred

Matching of Compressed Patterns with Character-Variables

pdf-format:
21.pdf (0.5 MB)

Abstract

We consider the problem of finding an instance of a string-pattern s in a given string under compression by straight line programs (SLP). The variables of the string pattern can be instantiated by single characters. This is a generalisation of the fully compressed pattern match, which is the task of finding a compressed string in another compressed string, which is known to have a polynomial time algorithm.
We mainly investigate patterns s that are linear in the variables, i.e. variables occur at most once in s, also known as partial words.
We show that fully compressed pattern matching with linear patterns can be performed in polynomial time. A polynomial-sized representation of all matches and all substitutions is also computed.
Also, a related algorithm is given that computes all periods of a compressed linear pattern in polynomial time. A technical key result on the structure of partial words shows that an overlap of h+2 copies of a partial word w with at most h holes implies that w is strongly periodic.

BibTeX - Entry

@InProceedings{schmidtschau:LIPIcs:2012:3498,
  author =	{Manfred Schmidt-Schau{\ss}},
  title =	{{Matching of Compressed Patterns with Character-Variables}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12) },
  pages =	{272--287},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Ashish Tiwari},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3498},
  URN =		{urn:nbn:de:0030-drops-34981},
  doi =		{10.4230/LIPIcs.RTA.2012.272},
  annote =	{Keywords: matching, grammar-based compression, partial words}
}

Keywords: matching, grammar-based compression, partial words
Collection: 23rd International Conference on Rewriting Techniques and Applications (RTA'12)
Issue Date: 2012
Date of publication: 29.05.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI