Function matching: Algorithms, applications, and a lower bound

Amihood Amir; Yonatan Aumann; Richard Cole; Moshe Lewenstein; Ely Porat

doi:10.1007/3-540-45061-0_72

Function matching: Algorithms, applications, and a lower bound

Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

We introduce a new matching criterion - function matching - that captures several different applications. The function matching problem has as its input a text T of length n over alphabet Σ_T and a pattern P = P[1]P[2] ⋯ P[m] of length m over alphabet Σ_P. We seek all text locations i for which, for some function f : Σ_P > Σ_T (f may also depend on i), the m-length substring that starts at i is equal to f(P[1])f(P[2])⋯f(P[m]). We give a randomized algorithm which, for any given constant k, solves the function matching problem in time O(n log n) with probability 1/n^k of declaring a false positive. We give a deterministic algorithm whose time is O(n|Σ_P|log m) and show that it is almost optimal in the newly formalized convolutions model. Finally, a variant of the third problem is solved by means of two-dimensional parameterized matching, for which we also give an efficient algorithm.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
Publisher	Springer Verlag
Pages	929-942
Number of pages	14
ISBN (Print)	3540404937, 9783540404934
DOIs	https://doi.org/10.1007/3-540-45061-0_72
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2719
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Color indexing
Function matching
Parameterized matching
Pattern matching
Protein folding
Register allocation

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45061-0_72

Cite this

Amir, A., Aumann, Y., Cole, R., Lewenstein, M., & Porat, E. (2003). Function matching: Algorithms, applications, and a lower bound. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, & G. J. Woeginger (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 929-942). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2719). Springer Verlag. https://doi.org/10.1007/3-540-45061-0_72

Function matching: Algorithms, applications, and a lower bound. / Amir, Amihood; Aumann, Yonatan; Cole, Richard et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Jos C. M. Baeten; Jan Karel Lenstra; Joachim Parrow; Gerhard J. Woeginger. Springer Verlag, 2003. p. 929-942 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2719).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Amir, A, Aumann, Y, Cole, R, Lewenstein, M & Porat, E 2003, Function matching: Algorithms, applications, and a lower bound. in JCM Baeten, JK Lenstra, J Parrow & GJ Woeginger (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2719, Springer Verlag, pp. 929-942. https://doi.org/10.1007/3-540-45061-0_72

Amir A, Aumann Y, Cole R, Lewenstein M, Porat E. Function matching: Algorithms, applications, and a lower bound. In Baeten JCM, Lenstra JK, Parrow J, Woeginger GJ, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 929-942. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45061-0_72

Amir, Amihood ; Aumann, Yonatan ; Cole, Richard et al. / Function matching : Algorithms, applications, and a lower bound. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Jos C. M. Baeten ; Jan Karel Lenstra ; Joachim Parrow ; Gerhard J. Woeginger. Springer Verlag, 2003. pp. 929-942 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{eff2b4abf48647218b2cf6a72aafc09a,

title = "Function matching: Algorithms, applications, and a lower bound",

abstract = "We introduce a new matching criterion - function matching - that captures several different applications. The function matching problem has as its input a text T of length n over alphabet ΣT and a pattern P = P[1]P[2] ⋯ P[m] of length m over alphabet ΣP. We seek all text locations i for which, for some function f : ΣP > ΣT (f may also depend on i), the m-length substring that starts at i is equal to f(P[1])f(P[2])⋯f(P[m]). We give a randomized algorithm which, for any given constant k, solves the function matching problem in time O(n log n) with probability 1/nk of declaring a false positive. We give a deterministic algorithm whose time is O(n|ΣP|log m) and show that it is almost optimal in the newly formalized convolutions model. Finally, a variant of the third problem is solved by means of two-dimensional parameterized matching, for which we also give an efficient algorithm.",

keywords = "Color indexing, Function matching, Parameterized matching, Pattern matching, Protein folding, Register allocation",

author = "Amihood Amir and Yonatan Aumann and Richard Cole and Moshe Lewenstein and Ely Porat",

year = "2003",

doi = "10.1007/3-540-45061-0_72",

language = "English (US)",

isbn = "3540404937",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "929--942",

editor = "Baeten, {Jos C. M.} and Lenstra, {Jan Karel} and Joachim Parrow and Woeginger, {Gerhard J.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Function matching

T2 - Algorithms, applications, and a lower bound

AU - Amir, Amihood

AU - Aumann, Yonatan

AU - Cole, Richard

AU - Lewenstein, Moshe

AU - Porat, Ely

PY - 2003

Y1 - 2003

N2 - We introduce a new matching criterion - function matching - that captures several different applications. The function matching problem has as its input a text T of length n over alphabet ΣT and a pattern P = P[1]P[2] ⋯ P[m] of length m over alphabet ΣP. We seek all text locations i for which, for some function f : ΣP > ΣT (f may also depend on i), the m-length substring that starts at i is equal to f(P[1])f(P[2])⋯f(P[m]). We give a randomized algorithm which, for any given constant k, solves the function matching problem in time O(n log n) with probability 1/nk of declaring a false positive. We give a deterministic algorithm whose time is O(n|ΣP|log m) and show that it is almost optimal in the newly formalized convolutions model. Finally, a variant of the third problem is solved by means of two-dimensional parameterized matching, for which we also give an efficient algorithm.

AB - We introduce a new matching criterion - function matching - that captures several different applications. The function matching problem has as its input a text T of length n over alphabet ΣT and a pattern P = P[1]P[2] ⋯ P[m] of length m over alphabet ΣP. We seek all text locations i for which, for some function f : ΣP > ΣT (f may also depend on i), the m-length substring that starts at i is equal to f(P[1])f(P[2])⋯f(P[m]). We give a randomized algorithm which, for any given constant k, solves the function matching problem in time O(n log n) with probability 1/nk of declaring a false positive. We give a deterministic algorithm whose time is O(n|ΣP|log m) and show that it is almost optimal in the newly formalized convolutions model. Finally, a variant of the third problem is solved by means of two-dimensional parameterized matching, for which we also give an efficient algorithm.

KW - Color indexing

KW - Function matching

KW - Parameterized matching

KW - Pattern matching

KW - Protein folding

KW - Register allocation

UR - http://www.scopus.com/inward/record.url?scp=35248829485&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248829485&partnerID=8YFLogxK

U2 - 10.1007/3-540-45061-0_72

DO - 10.1007/3-540-45061-0_72

M3 - Chapter

AN - SCOPUS:35248829485

SN - 3540404937

SN - 9783540404934

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 929

EP - 942

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Baeten, Jos C. M.

A2 - Lenstra, Jan Karel

A2 - Parrow, Joachim

A2 - Woeginger, Gerhard J.

PB - Springer Verlag

ER -

Function matching: Algorithms, applications, and a lower bound

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this