부산대학교 도서관

Summary: ``Given a sequence $A$ of length $M$ and a regular expression$R$ of length $P$, an approximate regular expression pattern matchingalgorithm computes the score of the best alignment between $A$ and oneof the sequences exactly matched by $R$. There are a variety ofschemes of scoring alignments. In a concave gap-penalty scoringscheme, a function $\delta (a,b)$ gives the score of each aligned pairof symbols $a$ and $b$, and a concave function $w(k)$ gives the scoreof a sequence of unaligned symbols, or gap, of length $k$. A function$w$ is concave if and only if it has the property that for all $k>1$,$w(k+1)-w(k)\leq w(k)-w(k-1)$. In this paper we present an $O(MP(\logM+\log^2 P))$ algorithm for approximate regular expression matchingfor an arbitrary $\delta$ and any concave $w$.''