Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1212627, author = {Ordyniak, Sebastian and Popa, Alexandru}, address = {Wroclaw}, booktitle = {Lecture Notes in Computer Science}, doi = {http://dx.doi.org/10.1007/978-3-319-13524-3_23}, editor = {Marek Cygan and Pinar Heggernes}, keywords = {parameterized complexity; generalized pattern matching}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Wroclaw}, isbn = {978-3-319-13523-6}, pages = {270-281}, publisher = {Springer}, title = {A Parameterized Study of Maximum Generalized Pattern Matching Problems}, year = {2014} }
TY - JOUR ID - 1212627 AU - Ordyniak, Sebastian - Popa, Alexandru PY - 2014 TI - A Parameterized Study of Maximum Generalized Pattern Matching Problems PB - Springer CY - Wroclaw SN - 9783319135236 KW - parameterized complexity KW - generalized pattern matching N2 - The generalized function matching (GFM) problem has been intensively studied starting with [Ehrenfeucht and Rozenberg, 1979]. Given a pattern p and a text t, the goal is to find a mapping from the letters of p to non-empty substrings of t, such that applying the mapping to p results in t. Very recently, the problem has been investigated within the framework of parameterized complexity [Fernau, Schmid, and Villanger, 2013]. In this paper we study the parameterized complexity of the optimization variant of GFM (called Max-GFM), which has been introduced in [Amir and Nor, 2007]. Here, one is allowed to replace some of the pattern letters with some special symbols ``?'', termed wildcards or don't cares, which can be mapped to an arbitrary substring of the text. The goal is to minimize the number of wildcards used. We give a complete classification of the parameterized complexity of Max-GFM and its variants under a wide range of parameterizations, such as, the number of occurrences of a letter in the text, the size of the text alphabet, the number of occurrences of a letter in the pattern, the size of the pattern alphabet, the maximum length of a string matched to any pattern letter, the number of wildcards and the maximum size of a string that a wildcard can be mapped to. ER -
ORDYNIAK, Sebastian a Alexandru POPA. A Parameterized Study of Maximum Generalized Pattern Matching Problems. In Marek Cygan and Pinar Heggernes. \textit{Lecture Notes in Computer Science}. Wroclaw: Springer, 2014, s.~270-281. ISBN~978-3-319-13523-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-13524-3\_{}23.
|