Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Lower Bounds for Kernelization Read chapter Read first chapter

2014 | OriginalPaper | Chapter

A Parameterized Study of Maximum Generalized Pattern Matching Problems

Authors : Sebastian Ordyniak, Alexandru Popa

Published in: Parameterized and Exact Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The generalized function matching (GFM) problem has been intensively studied starting with [7]. 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 [9].
In this paper we study the parameterized complexity of the optimization variant of GFM (called Max-GFM), which has been introduced in [1]. 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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Finite Integer Index of Pathwidth and Treewidth
next chapter Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
Literature
1.
2.
Angluin, D.: Finding patterns common to a set of strings (extended abstract). In: Proceedings of the 11h Annual ACM Symposium on Theory of Computing, 30 April–2 May, Atlanta, Georgia, USA, pp. 130–141 (1979)
3.
4.
Clifford, R., Harrow, A.W., Popa, A., Sach, B.: Generalised matching. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 295–301. Springer, Heidelberg (2009)CrossRef
5.
Clifford, R., Popa, A.: (In)approximability results for pattern matching problems. In: Holub, J., Zdárek, J. (eds.) Proceedings of the Prague Stringology Conference 2010, Prague, Czech Republic, 30 August–1 September, pp. 52–62. Prague Stringology Club, Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague (2010)
6.
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)CrossRef
7.
Ehrenfreucht, A., Rozenberg, G.: Finding a homomorphism between two words in np-complete. Inf. Process. Lett. 9(2), 86–88 (1979)CrossRef
8.
Fernau, H., Schmid, M.L.: Pattern matching with variables: a multivariate complexity analysis. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 83–94. Springer, Heidelberg (2013)CrossRef
9.
Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. In: Seth, A., Vishnoi, N.K. (eds). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013. LIPIcs, 12–14 December 2013, Guwahati, India, vol. 24, pp. 55–66. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)
10.
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol. XIV. Springer, Berlin (2006)
11.
Freydenberger, D.D., Reidenbach, D., Schneider, J.C.: Unambiguous morphic images of strings. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 248–259. Springer, Heidelberg (2005)CrossRef
12.
Jiang, T., Kinber, E., Salomaa, A., Salomaa, K., Yu, S.: Pattern languages with and without erasing. Int. J. Comput. Math. 50(3–4), 147–163 (1994)CrossRefMATH
13.
Mateescu, A., Salomaa, A.: Finite degrees of ambiguity in pattern languages. Inform. Théorique et Appl. 28(3–4), 233–253 (1994)MATHMathSciNet
14.
Ng, Y.K., Shinohara, T.: Developments from enquiries into the learnability of the pattern languages from positive data. Theor. Comput. Sci. 397(13), 150–165 (2008). Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf WiehagenCrossRefMATHMathSciNet
15.
Ordyniak, S., Popa, A.: A parameterized study of maximum generalized pattern matching problems. CoRR, abs/​1402.​6109 (2014)
16.
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757–771 (2003)CrossRefMATHMathSciNet
17.
18.
Reidenbach, D.: Discontinuities in pattern inference. Theor. Comput. Sci. 397(13), 166–193 (2008). Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf WiehagenCrossRefMATHMathSciNet
19.
Schmid, M.L.: A note on the complexity of matching patterns with variables. Inf. Process. Lett. 113(19–21), 729–733 (2013)CrossRefMATH
20.
Takeshi, S.: Polynomial time inference of extended regular pattern languages. In: Goto, E., Furukawa, K., Nakajima, R., Nakata, I., Yonezawa, A. (eds.) RIMS 1982. LNCS, vol. 147, pp. 115–127. Springer, Heidelberg (1983)CrossRef
Metadata
Title
A Parameterized Study of Maximum Generalized Pattern Matching Problems
Authors
Sebastian Ordyniak
Alexandru Popa
Copyright Year
2014
Book
Parameterized and Exact Computation

Print ISBN: 978-3-319-13523-6

Electronic ISBN: 978-3-319-13524-3

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-13524-3_23

Premium Partner

    Image Credits