Show simple item record

dc.contributor.authorAmir, Amihooden_US
dc.contributor.authorFarach-Colton, Martin
dc.contributor.authorMuthukrishnan, S.
dc.date.accessioned2005-06-17T18:04:06Z
dc.date.available2005-06-17T18:04:06Z
dc.date.issued1993en_US
dc.identifier.urihttp://hdl.handle.net/1853/6775
dc.description.abstractThe 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.extent147501 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-93-44en_US
dc.subjectParameterized matching
dc.subjectStrings
dc.subjectAlphabet sets
dc.subjectComparison models
dc.subjectStandard string matching
dc.titleAlphabet Dependence in Parameterized Matchingen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record