Alphabet Dependence in Parameterized Matching

Show simple item record

dc.contributor.author Amir, Amihood en_US
dc.contributor.author Farach-Colton, Martin
dc.contributor.author Muthukrishnan, S.
dc.date.accessioned 2005-06-17T18:04:06Z
dc.date.available 2005-06-17T18:04:06Z
dc.date.issued 1993 en_US
dc.identifier.uri http://hdl.handle.net/1853/6775
dc.description.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. en_US
dc.format.extent 147501 bytes
dc.format.mimetype application/pdf
dc.language.iso en_US
dc.publisher Georgia Institute of Technology en_US
dc.relation.ispartofseries CC Technical Report; GIT-CC-93-44 en_US
dc.subject Parameterized matching
dc.subject Strings
dc.subject Alphabet sets
dc.subject Comparison models
dc.subject Standard string matching
dc.title Alphabet Dependence in Parameterized Matching en_US
dc.type Technical Report eng_US


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 simple item record