Akademska digitalna zbirka SLovenije - logo
E-resources
Full text
Peer reviewed
  • A brief history of paramete...
    Mendivelso, Juan; Thankachan, Sharma V.; Pinzón, Yoan

    Discrete Applied Mathematics, 03/2020, Volume: 274
    Journal Article

    Parameterized pattern matching is a string searching variant that was initially defined to detect duplicate code but later proved to support several other applications. In particular, two equal-length strings X andY are a parameterized-match if there exists a bijective function g for which every text symbol in X is equal to g(Y). Baker was the first researcher to have addressed this problem (Baker, 1993) and, since then, many others have followed her work. She did, indeed, open up a wide field of extensive research. Over the years, many variants and extensions that have been pursued include: parameterized matching under edit and Hamming distances, parameterized multi-pattern matching, two dimensional parameterized matching, structural matching, function matching, and the very recent developments in succinct and streaming models. This accelerated research could only be justified by the usefulness of its practical applications such as in software maintenance, image processing and bioinformatics to name some. Even though the problem was posed about 25 years ago, research on parameterized matching is still very active. Its extensive study over the years and its current relevance motivate us to review the most notorious contributions as road map for current and future research.