Mining Maximal Flexible Patterns in a
Sequence?
Hiroki Arimura1 , Takeaki Uno2
1

Graduate School of Information Science and Technology, Hokkaido University
Kita 14 Nishi 9, Sapporo 060-0814, Japan
arim@ist.hokudai.ac.jp
2
National Institute of Informatics
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
uno@nii.jp

Abstract. We consider the problem of enumerating all maximal

flexible patterns in an input sequence database for the class of flexible patterns, where a maximal pattern (also called a closed pattern)
is the most specific pattern among the equivalence class of patterns
having the same list of occurrences in the input. Since our notionof maximal patterns is based on position occurrences, it is weaker
than the traditional notion of maximal patterns based on document
occurrences. Based on the framework of reverse search, we present
an efficient depth-first search algorithm MaxFlex for enumerating
all maximal flexible patterns in a given sequence database without
duplicates in O(||T || × |Σ|) time per pattern and O(||T ||) space,
where ||T || is the size of the input sequence database T and |Σ| isthe size of the alphabet on which the sequences are defined. Thismeans that the enumeration problem for maximal flexible patterns
is shown to be solvable in polynomial delay and polynomial space.

1

Introduction

The rapid growth of fast networks and large-scale storage technologies has led
to the emergence of a new kind of massive data called semi-structured data
emerged, which is a collection of weakly structured electronic data modeled by
combinatorial structures, such as sequences, trees, and graphs. Hence, demand
has arisen for efficient knowledge discovery algorithms for such semi-structureddata.
In this paper, we consider the maximal pattern discovery problem for theclass of flexible patterns in a sequence database [6, 7, 11, 12], which is also called
the closed sequence mining problem [11, 12]. A flexible pattern is a sequence of?

This research was partly supported by the Ministry of Education, Science, Sports andCulture, Grant-in-Aid for Specially Promoted Research, 17002008, 2007 on “semistructured data mining”, and 18017015, 2007 on “developing high-speed high-quality
algorithms for analyzing huge genome database”.

1

constant strings separated by special gap symbols ’∗’ such as AB*B*ABC, whichmeans that the substring AB appears first in the input sequence, followed by B andthen ABC. A pattern is maximal w.r.t. position occurrences in a sequence database
if there is no properly more specific pattern that has the same set of occurrencesin the input sequences. Thus, the maximal flexible pattern discovery problem isto enumerate all maximal flexible patterns in a given sequence database without
duplicates.
For any minimum frequency threshold parameter σ ≥ 0, the set of all frequent
maximal patterns Mσ in input sequences contains complete information on theset of all frequent patterns Fσ , and furthermore, Mσ is typically much smaller
than Fσ if σ is small. Thus, the solution for maximal pattern discovery has the
merit of increasing both efficiency and comprehensiveness of frequent patternmining. On the other hand, the (frequent) maximal pattern discovery problem
has high computational complexity compared with frequent pattern discovery.
Thus, we need a lightweight and fast mining algorithm to solve the maximal
pattern problem. In terms of algorithm theory, the efficiency of such enumeration algorithms is evaluated according to the worst-case computation time persolution. Particularly, if the algorithm works in polynomial space in terms of
the input size, and the maximum time required to output the next pattern after
outputting the previous one, called the delay, is of polynomial order of the input
size, the algorithm said to be good.
As related works, Wang and Han [12] gave an efficient maximal pattern discovery algorithm BIDE for the class SP of sequential episodes [5] or subsequence
patterns [12], where an episode is a pattern of the form a1 ∗ · · · ∗ an (ai ∈ Σ, 1 ≤i ≤ n). Arimura and Uno [4, 6] gave a polynomial delay and polynomial timealgorithm MaxMotif for maximal pattern discovery for the class RP of rigid
patterns (or motifs with wildcards) [7], where a rigid pattern is of the form
w1 ◦ · · · ◦ wn (wi ∈ Σ ∗ , 1 ≤ i ≤ n) for a single symbol wildcard ◦. However, nopolynomial space and polynomial delay algorithm, or even no output polynomial
time algorithm, has been known for the maximal pattern discovery problem forthe class FP of flexible patterns. Here maximal patterns in FP are the patterns which are maximal among the patterns appearing at the same locations(or positions) of the given sequence database.
As a main result of this paper, for the class FP of flexible patterns, we
present an efficient depth-first search algorithm MaxFlex that enumerates all
maximal patterns P ∈ FP in a given sequence database T without duplicatesin O(|Σ| × ||T ||) time per maximal pattern using O(||T ||) space, where ||T || isthe size of T , and |Σ| is the size of the alphabet. A key to the algorithm is a
depth-first search tree built on maximal patterns based on the reverse searchframework [1]. Besides this, we discuss how to implement an efficient location
list computation and maximality test. As a corollary, we show that the maximal
pattern discovery problem for the class FP of flexible patterns is polynomial
space and polynomial delay solvable. This result properly generalizes the outputpolynomial complexity of the class SP of subsequence patterns [12].
2The organization of this paper is as follows. In Section 2, we introduce theclass FP of flexible patterns and define our data mining problem. We show
an adjacency relation between maximal flexible patterns that implicitly induces
a tree-shaped search route in Section 3, and describe algorithm MaxFlex that
performs a depth-first search on the search route in Section 4. We conclude thispaper in Section 5.

2

Preliminaries

Let Σ be an alphabet of symbols. We denote the set of all possibly empty strings
and the set of all non-empty finite strings over Σ by Σ ∗ and Σ + = Σ ∗ − {ε},respectively. Let s = a1 · · · an ∈ Σ ∗ be a string over Σ of length n. We denotethe length of s by |s|, i.e., |s| = n. The string with no symbol is called an empty
string, and it is denoted by ε. For any 1 ≤ i ≤ j ≤ n, we denote the i-th symbolof s by s[i] = ai . For i and j such that 1 ≤ i ≤ j ≤ |s|, the string ai · · · aj iscalled a substring of s, and denoted by s[i..j]. We say that a substring v occurs
in s at position i iff v = s[i..j]. For two strings s = a1 · · · an and t = b1 · · · bn ,the concatenation of t to s is the string s = a1 · · · an b1 · · · bn , and denoted bys • t or simply st. A string u is called a prefix of s if s = uv holds for some stringv, and is called a suffix of s if s = vu holds for some v. For a set S of strings, wedenote the cardinality of S by |S|. The sum of the string lengths in S is called
the total size of S and denoted by ||S||.
2.1

Patterns and their location lists

We introduce the class FP of flexible patterns [6], also known as erasing regularpatterns. Let Σ = {a, b, c, . . .} be a finite alphabet of constant symbols. A gap or
a variable-length don’t care, (VLDC ) is a special symbol ∗ 6∈ Σ, which represents
an arbitrarily long possibly-empty finite string in Σ ∗ . A constant string is a string
composed only of constant symbols. A flexible pattern (pattern, for short) over
Σ is a sequence P = w0 ∗ w1 ∗ · · · ∗ wd of non-empty constant strings separated
by gap symbols, where each constant string wi ∈ Σ + , (0 ≤ i ≤ d, d ≥ 0)
is called a segment of P . w0 is called the first segment of P and denoted by
seg0 (P ). w1 ∗ · · · ∗ wd is called the segment suffix of P , and denoted by sf x0 (P ).
A flexible pattern is called an erasing regular pattern in the field of machinelearning (Shinohara [10]) and a VLDC pattern in the field of pattern matching.
Pd
The size of P is |P | = i |wi |. For every d ≥ 0, a d-pattern is a pattern withd + 1 segments. We denote the class of flexible patterns over Σ by FP. Clearly,Σ + ⊆ FP.
Example 1. Let Σ = {A, B, C}. Then, P0 = AB, P1 = A∗B, P2 = AB ∗A∗ABC
are flexible patterns.
Let P = w0 ∗· · ·∗wd ∈ FP, wi ∈ Σ + be a d-pattern (d ≥ 0). A substitution for
P is a d-tuple θ = (u1 , . . . , ud ) ∈ FP d of non-empty constant strings. We define
the application of θ to P , denoted by P θ, as the string P θ = w0 u1 w1 u2 · · · ud wd ∈FP, where the i-th occurrence of the variable ∗ is replaced with the i-th string ui
3

012345678

Pattern P

Text T

AB*CBA*BBBCBCABDCBCBABACBBABAB

m=9n = 21012345678901234567890
00
10
20

p = 4 An occurrence position p of P in T

Fig. 1. A flexible pattern P and its position in a constant string T .

for every i = 1, . . . , d. The string P θ is said to be an instance of P by substitutionθ.
We define a binary relation v over P, called the specifity relation, as follows [2, 6, 10]. A position in a flexible pattern P is a number p ∈ {1, . . . , |P |}.
Here each position i means the position of ith constant symbol.
For flexible patterns P, Q ∈ F P, we say P occurs in Q if there exists a
substitution θ such that α(P θ)β = Q holds for some α, β ∈ F P. We say P
occurs in Q at position |α| + 1. Here |α| also means the number of constantsymbols in α. The location list for P in Q, denoted by LO(P, Q) is the set of all
possible positions of pattern P in Q.
If P occurs in Q we say that either Q is more specific than P or P is moregeneral than Q, and write P v Q. If both P v Q and Q 6v P hold, we say Q isproperly more specific than P and write P < Q. Note that P = Q holds if andonly if P v Q and Q v P hold.
Lemma 1. (FP, v) is a partial ordering with the smallest element ε.
Example 2. For patterns P3 = A ∗ BA ∗ B and P4 = BAB ∗ BA ∗ AB ∗ B, we cansee that P3 v P4 by the embedding BAB ∗ BA ∗ AB ∗ B, where the image of P4
is indicated by underlines. Formally, P3 v P4 holds because P3 has an instanceP3 θ = AB ∗ BA ∗ AB as a substring of P4 for the substitution θ = (B∗, ∗A).
Clearly, P3 < P4 since P3 v P4 but P4 6v P3 .
A sequence database T = {T1 , . . . , Tm } is a set of constant strings Ti ∈ Σ ∗ .
We denote the number of strings by m. The sum ofP
the sizes of T1 , . . . , Tm ismcalled the size of T and denoted by ||T ||, i.e., ||T || = i=1 |Ti |. In what follows,
we fix the sequence database unless stated otherwise. For a flexible pattern P
and a set of flexible patterns T , which can be a sequence database, the location
set for P in T , denoted by LO(P, T ) is the set of location lists LO(P, Ti ) in all
Ti ∈ T .
For flexible patterns P and Q, the largest position in LO(P, Q) is called therightmost position of P in Q, and denoted by pmax (P, Q). If LO(P, Q) is empty,4

we define pmax (P, Q) as −∞. If P is an empty sequence, we define pmax (P, Q)
as |Q| + 1.
Lemma 2. For any P, T ∈ FP, LO(P, T ) = {p | p ∈ LO(seg0 (P ), T ), p +|seg0 (P )| ≤ pmax (sf x0 (P ), T )}.
The frequency f rq(P, T ) of a flexible pattern P in a sequence database T
is |LO(P, T )| = |{LO(P, Ti ) | Ti ∈ T , LO(P, Ti ) 6= ∅}|. A minimum support
threshold is a non-negative integer 0 < σ ≤ n. A flexible pattern P is σ-frequent
in T if its frequency in T is no less than σ, i.e., f rq(P, T ) ≥ σ.
2.2

Maximal pattern enumeration problem

Definition. 1 A flexible pattern P is maximal in T if there is no proper specialization Q of P that has the same location list, that is, there is no Q ∈ FP
such that P < Q and LO(P, T ) = LO(Q, T ).
We see that a pattern P ∈ FP is maximal iff P is a maximal element w.r.t. v
in the equivalence class [P ]T = {Q ∈ F P|P ≡T Q} under the equivalence
relation ≡T over FP defined by P ≡T Q ⇔ LO(P, T ) = LO(Q, T ).
Lemma 3. The maximal patterns in each equivalence class [P ]T are not uniquein general.
We denote the family of the maximal patterns in T by M, and the familyof σ-frequent flexible patterns by Fσ . Let Mσ = Fσ ∩ M be the family of σfrequent maximal patterns. It is easy to see that the number of frequent flexible
patterns in T can be exponential in ||T || and the same is true for Mσ .
Lemma 4. There is an infinite sequence T1 , T2 , . . . of sequence databases suchthat the number of maximal flexible patterns in Ti is exponential in ||Ti ||.
Now, we state our data mining problem as follows.
Position Maximal Flexible Pattern Enumeration Problem:
Input: sequence database T over an alphabet Σ, a minimum support thresholdσ
Output: all maximal σ-frequent flexible patterns in Mσ in T without duplicates
Our goal is to develop an efficient enumeration algorithm for this problem.

3

Tree-shaped Search Route for Maximal Flexible
Patterns

In this section, we introduce a tree-shaped search route R spanning all elements
in M. In section 4, we give a memory efficient algorithm for enumerating all
maximal flexible patterns based on the depth-first search over R. Our strategy is
as follows: First we define a binary relation between maximal patterns, called theparent function, which indicates a directed edge from a child to its parent. The
5

parent function induces an adjacency relation on M, whose form is a spanningtree.
We start with several technical lemmas.
Definition. 2 A flexible pattern Q is said to be a prefix specialization of anotherflexible pattern P if 1 ∈ LO(P, Q). If Q is a specialization of P but not a prefix
specialization, Q is said to be a non-prefix specialization of P .
The following two lemmas are essential for flexible patterns. The first one
says that a limited kind of monotonicity holds for flexible patterns. The proof is
obvious from the transitivity of the specialization relation.
Lemma 5. For any P, Q, T ∈ FP if P is a prefix specialization of Q, thenLO(P, T ) ⊇ LO(Q, T ).
The second lemma gives us a technical property that a non-prefix specialization of P always has a location list different from that of P . Thus, attaching a
new symbol to the left of a flexible pattern never preserves its location list.
Lemma 6. Let T, P, Q ∈ FP such that P < Q v T . Then, if Q is a non-prefix
specialization of P then LO(P, T ) 6= LO(Q, T ).
Proof. Since Q is a specialization of P but not a prefix specialization, LO(P, Q)
includes a position p > 1. This means that P occurs in T [pmax (Q, T )+p−1..|T |],thus pmax (P, T ) 6= pmax (Q, T ). This implies LO(P, T ) 6= LO(Q, T ).
utCorollary 1. A flexible pattern Q ∈ FP is maximal if and only if none of its
prefix specializations has a location list equal to Q.
Definition. 3 The parent P(P ) of a flexible pattern P is the flexible patternobtained from P by removing its first symbol and ∗ if the following operator is∗.
Lemma 7. For any non-empty flexible pattern Q ∈ FP, its parent is always
defined and unique.
Lemma 8. For any non-empty flexible pattern P and constant symbol a, LO(a•P, T ) = {p ∈ LO(a, T ) | p+1 ∈ LO(P, T )}, and LO(a∗P, T ) = {p ∈ LO(a, T ) | p <pmax (P, T )}.
Corollary 2. For any flexible pattern P , f rq(P, T ) ≤ f rq(P(P ), T ).
The proof of the above lemma is omitted, but it is not difficult. A root pattern
in T is a maximal pattern P such that LO(P, T ) = LO(ε, T ). The root patternis either ε or a symbol a if all symbols in any sequence T ∈ T are a. Now, weare ready for the main result of this section.
Theorem 1 (reverse search property of M). Let Q ∈ M be a maximal
flexible pattern in T that is not a root pattern. Then, P(Q) is also a maximal
flexible pattern in T , that is, if Q ∈ M then P(Q) ∈ M holds.
6

Proof. Let Q be a maximal flexible pattern that is not a root pattern. To prove
the theorem by contradiction, we suppose that there is a proper specialization P 0of P(Q) such that LO(P(Q), T ) = LO(P 0 , T ). If P 0 is not a prefix specializationof P(Q), then from Lemma 6, we see that LO(P, T ) 6= LO(P 0 , T ). Thus, weconsider the case that P 0 is a prefix specialization of P(Q).
From the definition of the parent, Q = a } P(Q) for some a ∈ Σ and } ∈{•, ∗}. Let Q0 = a } P 0 ∈ F P. Since P 0 is a proper prefix specialization of
P(Q), Q0 is also a proper prefix specialization of Q. Let T be a sequence in T
and p be a position p ∈ LO(Q, T ). If } = •, then p + 1 ∈ LO(P(Q), T ) andthus also p + 1 ∈ LO(P 0 , T ). Thus we have p ∈ LO(Q0 , T ). If } = ∗, thenp < pmax (P(Q), T ) thus also p < pmax (P 0 , T ). Thus, we have p ∈ LO(Q0 , T ). In
both cases, we have LO(Q, T ) ⊆ LO(Q0 , T ), thus LO(Q, T ) = LO(Q0 , T ). This
immediately implies that LO(Q, T ) = LO(Q0 , T ), contradiction.
utDefinition. 4 A search route for M w.r.t. P is a directed graph R = (M, P, ⊥)with root, where M is the set of nodes, i.e., the set of all maximal flexible patterns
in T , P is the set of reverse edge such that (P, Q) ∈ P iff P = P(Q) holds, and⊥ ∈ M is the root pattern in T .
Since each non-root node has its parent in M by Theorem 1 and |P(P )| < |P |,the search route R is actually a directed tree with reverse edges. Therefore, wehave the following corollary.
Corollary 3. For any sequence database T , R = (M, E, ⊥) forms a rooted spanning tree with the root ⊥.
We have the following lemma on the shape of T .
Lemma 9. Let P ∈ M be any maximal pattern in T and m = |P |. Then,(i) the depth of P in T (the length of the unique path from the root to P ) is at
most m.
(ii) the branching of P in T (the number of the children for P ) is at most 2|Σ|.

4

A Polynomial Time and Polynomial Delay Algorithm

In Figure 2 shows a polynomial space and polynomial delay enumeration algorithm MaxFlex for maximal flexible patterns. This algorithm starts from thebottom pattern ⊥ and searches from smaller to larger all maximal patterns in a
depth-first search manner over the search route R.
However, since the search route R is defined by the reverse edges from children to their parents, it is not an easy task to traverse the edges. We firstly
explain how to compute all children of given parent pattern P ∈ M. The following lemma ensures that any child can be obtained by attaching a new symbolwith an operator to the left of P .
Lemma 10. For any maximal flexible patterns P, Q ∈ M, P = P(Q) if andonly if Q is maximal, and Q = a } P holds for some constant symbol a ∈ Σ and} ∈ {•, ∗}.
7

Algorithm MaxFlex(Σ, T , σ):input: sequence database T on an alphabet Σ s.t. any T ∈ T is in Σ ∗ , minimum support threshold σ
output: All maximal patterns in Mσ
1 compute the root pattern ⊥ //the maximal pattern in T equivalent to ε
2 ExpandMaxFlex(⊥, LO(⊥, T ), T, σ);Procedure ExpandMaxFlex(P, LO(P, T ), T , σ):input: maximal pattern P , location list LO(P, T ), sequence database T , minimum support threshold σ
output: all maximal patterns in Mσ that are descendants of P
1 if f rq(P, T ) < σ then return
2 if P is not maximal in T then return
3 output P
4 foreach pair of a ∈ Σ and } ∈ {•, ∗} do begin
5
ExpandMaxFlex(a } P, LO(a } P, T ), T )6 end
Fig. 2. An algorithm MaxFlex for enumerating all maximal flexible patterns in a sequence database.

Since P(Q) is defined for any non-empty pattern Q, we know from Lemma 10
that any flexible pattern can be obtained from ⊥ by a finite number of applications of the operator • or ∗. Therefore, Theorem 1 ensures that we can correctly
prune all descendants of the current pattern P if it is no longer maximal in
depth-first search of M. Moreover, if f rq(P, T ) < σ, no descendant of P isfrequent. Thus, we can also prune the descendants.
Secondly, we discuss the computation time of the algorithm. The bottleneckof the computation is the check of the maximality of the current pattern P , thus
we need an efficient way to test it.
The notion of the refinement operator was introduced by Shapiro [8]. The
refinement operator for flexible patterns in FP, under the name of erasing regular patterns, was introduced by Shinohara [10]. The following version is due to[2, 3].
Definition. 5 Let P ∈ FP, P = w0 ∗ · · · ∗ wd be any flexible pattern. Then,
we define the set ρ(P ) ⊆ FP as the set of all patterns Q ∈ FP, called basic
refinements of P if Q is obtained from P by one of the following operations:(1) replace wi by wi ∗ a for some a ∈ Σ and 0 ≤ i ≤ d.
(2) replace wi ∗ wi+1 by wi wi+1 for some 0 ≤ i ≤ d − 1.
Lemma 11. A flexible pattern P is maximal in T if and only if there is no basic
refinement Q ∈ ρ(P ) such that LO(P, T ) = LO(Q, T ).
Suppose that P and T are flexible patterns and the segments of a flexible
pattern P are w0 , . . . , wd . Let lef t(P, T, i), 0 ≤ i ≤ d be the minimum position p
8such that T [1..p] is a specification of w0 ∗ · · · ∗ wi . If T is not a specification of P ,lef t(P, T, i) is defined by +∞. If P is an empty sequence, we define lef t(P, T, i) =0.
For any segment w and position p in T , let succ(w, T, p) be the smallest
position q such that q ≥ p and q ∈ LO(w, T ). For any string w, computing
succ(w, T, p) for all pairs of T ∈ T and p ∈ LO(w, T ) can be done in O(||T ||)time.
Lemma 12. There is a basic refinement obtained by replacing wi by wi ∗ ahaving the same location list as P if and only if there is a common symbol inT [lef t(P, T, i) + 1..pmax (wi+1 ∗ · · · ∗ wd , T ) − 1] for all T ∈ T .
Proof. The if part of the statement is obvious. We check the “only if” part,by showing that there is a common symbol a. Suppose that a basic refinement
obtained by replacing wi by wi ∗ a has the same location list as P . Then for any
T ∈ T , there is a position q such that T [q] = a, T [1..q − 1] is a specification of
w0 ∗ · · · ∗ wi , and T [q + 1..|T |] is a specification of wi+1 ∗ · · · ∗ wd . Then, fromthe definition of pmax and lef t, lef t(P, T, i) < q < pmax (wi+1 ∗ · · · ∗ wd , T ). This
states the statement of the lemma.
utSimilarly, we obtain the following lemma.
Lemma 13. There is a basic refinement obtained by replacing wi ∗ wi+1 by
wi wi+1 having the same location list as P if and only if succ(wi wi+1 , T, lef t(P, T, i−1)) + |wi wi+1 | ≤ pmax (wi+2 ∗ · · · ∗ wd , T ) for any T ∈ T .
Lemma 14. Using lef t, succ, and pmax , we can determine whether there is abasic refinement having the same location list as P in O(||T ||) time.
Proof. The statement is clear for basic refinements obtained by replacing wi ∗wi+1 by wi wi+1 . Thus, we consider basic refinements obtained by replacing wi
by wi ∗ a.
Let Count(a, i), a ∈ Σ, 0 ≤ i ≤ d be the number of sequences T ∈ T suchthat T [lef t(P, T, i) + 1..pmax (wi+1 ∗ · · · ∗ wd , T ) − 1] includes a. What we haveto do is to check whether Count(a, i) = m holds for some a ∈ Σ or not. For any
i, Count(a, i) for all a ∈ Σ can be computed in O(||T ||) time.
For i > 0, let dif f (P, T, i) be the set of symbols with signs, such as +a, −a, +b, −b,such that +a is included in dif f (P, T, i) iff T [lef t(P, T, i − 1) + 1..pmax (wi ∗ · · · ∗wd , T ) − 1] does not include a but T [lef t(P, T, i) + 1..pmax (wi+1 ∗ · · · ∗ wd , T ) − 1]
includes a, and −a is included in dif f (P, T, i) iff T [lef t(P, T, i−1)+1..pmax (wi ∗· · ·∗wd , T )−1] includes a but T [lef t(P, T, i)+1..pmax (wi+1 ∗· · ·∗wd , T )−1] does
not include a. Using dif f (P, T, i), Count(a,P i + 1) for all a ∈ Σ can be obtained
from Count(a, i − 1) of all a ∈ Σ in O( T ∈T |dif f (P, T, i)|) time. Since eachdif f (P, i, T ) can be computed in O((lef t(P, T, i)−lef t(P, T, i−1))+(pmax (wi+1 ∗· · · ∗ wd , T ) − pmax (wi ∗ · · · ∗ wd , T ))) time, computing dif f (P, i, T ) for all pairsof i, 1 ≤ i ≤ d and T ∈ T takes O(||T ||) time. This concludes the lemma.
utLemma 15. Using succ, lef t(P, T, i) for all T ∈ T can be computed in O(||T ||)time.
9By combining the above lemmas, we get the main result of this paper, whichsays that MaxFlex is a memory and time efficient algorithm.
Theorem 2. Let Σ be an alphabet, T a sequence database, and σ a minimum
support threshold. Then, the algorithm MaxFlex in Fig. 2 enumerates all maximal
flexible patterns P ∈ Mσ of T without duplicates in O(|Σ| × ||T ||) time per
maximal flexible pattern within O(||T ||d) space, where d is the maximum numberof gaps in a flexible pattern P ∈ Mσ .
Proof. The correctness of the algorithm is clear, thus we discuss the complexity.
From Lemmas 14 and 15, the computation time for checking the maximality ofa flexible pattern can be done in O(||T ||) time, by using pmax and succ. For thetask, succ is needed only for segments w and consecutive segments ww0 in thecurrent pattern P . Thus, the memory complexity is O(||T ||d).
We next show how much time we need to compute those for a flexible patterna } P by using those for P . Actually, for any i > 0 and position p, succ(wi , T, p),succ(wi wj , T, p), and pmax (wi ∗ · · · ∗ wd , T ) are common to P and P 0 , hence wehave to compute those only for i = 0. Thus, it can be done in O(||T ||) time. We
have at most 2|Σ| candidates for the children of a maximal flexible pattern, thus
the statement holds.
ut
The delay of an enumeration algorithm is the maximum computation time
between a pair of consecutive outputs.
Corollary 4. The maximal pattern enumeration problem for the class FP of
flexible patterns w.r.t. position maximality is solvable in polynomial delay andpolynomial space in the input size.

5

Conclusion

In this paper, we considered the maximal pattern discovery problem for theclass FP of flexible patterns [6], which are also called erasing regular patterns inmachine learning. The motivation of this study is the potential application to the
optimal pattern discovery problem in machine learning and knowledge discovery.
Our main result was a polynomial space and polynomial delay algorithm forenumerating all maximal patterns appearing in a given string without duplicatesin terms of position-maximality defined through the equivalence relation between
the location sets. Extending this work to document-based maximal patterns andto more complex classes of flexible patterns are interesting future problems.

Acknowledgments
The authors would like to thank Tetsuji Kuboyama, Akira Ishino, Kimihito
Ito, Shinichi Shimozono, Takuya Kida, Shin-ichi Minato, Ayumi Shinohara,
Masayuki Takeda, Kouichi Hirata, Akihiro Yamamoto, Thomas Zeugmann, and
Ken Satoh, for their valuable discussions and comments. The authors also thankthe anonymous referees for their valuable comments that greatly improved thequality of this paper.
10

References
1. D. Avis and K. Fukuda, Reverse Search for Enumeration, Discrete Appl. Math.,
65, 21–46, 1996.
2. H. Arimura, R. Fujino, T. Shinohara, Protein motif discovery from positive examples by minimal multiple generalization over regular patterns, In Proc. GIW’94,
39-48, 1994.
3. H. Arimura, T. Shinohara, S. Otsuki, Finding minimal generalizations for unionsof pattern languages and its application to inductive inference from positive data,
In Proc. STACS’94, Springer, LNCS 775, 649–660, 1994.
4. H. Arimura, T. Uno, A polynomial space and polynomial delay algorithm forenumeration of maximal motifs in a sequence, In Proc. ISAAC’05, LNCS 3827,
Springer, Dec. 2005.
5. H. Mannila, H. Toivonen, A. I. Verkamo, Discovery of frequent episodes in event
sequences, Data Min. Knowl. Discov., 1(3), 259–289, 1997.
6. L. Parida, I. Rigoutsos, et al., Pattern discovery on character sets and real-valued
data: linear-bound on irredandant motifs and efficient polynomial time algorithms,
In Proc. SODA’00, SIAM-ACM, 2000.
7. N. Pisanti, M. Crochemore, R. Gross, M.-F. Sagot, A basis of tiling motifs for generating repeated patterns and its complexity of higher quorum, In Proc. MFCS’03,
Springer, 2003.
8. E. Y. Shapiro, Algorithmic Program Debugging, MIT Press, 1982.
9. S. Shimozono, H. Arimura, S. Arikawa, Efficient discovery of optimal wordassociation patterns in large text databases, New Generation Comput., 18(1),49–60, 2000.
10. T. Shinohara, Polynomial time inference of extended regular pattern Languages.
Proc. RIMS Symp. on Software Sci. & Eng., 115–127, 1982.
11. X. Yan and J. Han, R. Afshar, CloSpan: mining closed sequential patterns in large
databases, In Proc. SDM 2003, SIAM, 2003.
12. J. Wang and J. Han, BIDE: efficient mining of frequent closed sequences, In
Proc. ICDE’04, 2004.

11