Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Pattern Matching with Variables: A Multivariate Complexity Analysis
(Extended Abstract)
verfasst von : Henning Fernau, Markus L. Schmid
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the context of this paper, a pattern is a string that contains variables and terminals. A pattern
α
matches a terminal word
w
if
w
can be obtained by uniformly substituting the variables of
α
by terminal words. It is a well-known fact that deciding whether a given terminal word matches a given pattern is an NP-complete problem. In this work, we consider numerous parameters of this problem and for all possible combinations of these parameters, we investigate the question whether or not the variant obtained by bounding these parameters by constants can be solved efficiently.