Alphabet Dependence in Parameterized Matching

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6775

Title: Alphabet Dependence in Parameterized Matching
Author: Amir, Amihood ; Farach-Colton, Martin ; Muthukrishnan, S.
Abstract: The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set ∑. A recently introduced model is that of parameterized pattern matching; the main motivation for this scheme lies in software maintenance where programs are considered "identical" even if variables are different. Strings, under this model, additionally have symbols from a variable set Π and occurrences of one string in the other up to a renaming of the variables are sought. In this paper we show that finding the occurrences of a m-length string in a n-length string under the parameterized pattern matching paradigm can be done in time O (n log π), where π = min (m, ∣Π∣); that is , independent of ∣∑∣. Additionally, we show that in general this dependence on ∣Π∣ is inherent to any algorithm for this problem in the comparison model – that is, our algorithm is optimal.
Type: Technical Report
URI: http://hdl.handle.net/1853/6775
Date: 1993
Relation: CC Technical Report; GIT-CC-93-44
Publisher: Georgia Institute of Technology
Subject: Parameterized matching
Strings
Alphabet sets
Comparison models
Standard string matching

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GIT-CC-93-44.pdf 144.0Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record