Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Matching Patterns with Variables
verfasst von : Florin Manea, Markus L. Schmid
Erschienen in: Combinatorics on Words
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 (Link öffnet in neuem Fenster)
Abstract
A pattern \(\alpha \) (i. e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of \(\alpha \) by terminal words. The respective matching problem, i. e., deciding whether or not a given pattern matches a given word, is generally 
-complete, but can be solved in polynomial-time for classes of patterns with restricted structure. In this paper we overview a series of recent results related to efficient matching for patterns with variables, as well as a series of extensions of this problem.
-complete, but can be solved in polynomial-time for classes of patterns with restricted structure. In this paper we overview a series of recent results related to efficient matching for patterns with variables, as well as a series of extensions of this problem.
