Polynomial Space and Delay Algorithms for Enumeration of
Maximal Motifs in a Sequence
Hiroki Arimura1? and Takeaki Uno2
1

Hokkaido University, Kita 14-jo, Nishi 9-chome, Sapporo 060-0814, JAPANarim@ist.hokudai.ac.jp
2
National Institute of Informatics, Tokyo 101–8430, JAPAN
uno@nii.jp

Abstract. In this paper, we consider the problem of finding all maximal motifs in an input
string for the class of repeated motifs with wild cards. A maximal motif is such a representative motifs that is not properly contained in larger motifs with the same location
lists. The enumeration problem for maximal motifs with wild cards has been introduced in(Parida et al., SODA’00, CPM’01), and has been studied in (Parida et al., CPM’01), (Pisantiet al.,MFCS’03) and (Pelfrene et al., CPM’03). However, its output-polynomial time computability, in particular, with polynomial space and delay is still open. The main result of thispaper is a polynomial space polynomial delay algorithm for the maximal motif enumeration
problem for the repeated motifs with wild cards. This algorithm enumerates all maximal
motifs in an input string of length n with O(n3 ) time per motif with O(n2 ) space and O(n3 )delay by depth-first search. The key of the algorithm is a tree-shaped search route over all
maximal motifs based on a technique called prefix-preserving closure extension, which enable us to enumerate all maximal motifs without storing all discovered motifs. We also show
exponential lower bound and succinctness results on the number of maximal motifs, whichindicate the limit of a straightforward approach.

Keywords: enumeration problems, sequence pattern discovery, basis of tiling motifs,
bioinformatics, output-polynomial time algorithms
Correspondence:
Hiroki Arimura
Graduate School of Information Science and Technology
Hokkaido University
N14 W9, 060-0814 Sapporo, Japane-mail: arim@ist.hokudai.ac.jp
phone: +81-11-706-7678, fax: +81-11-706-7890?

This work is done during the first author’s visit in LIRIS, University Claude-Bernard Lyon 1, France.

1

Introduction

Pattern discovery is to find all patterns within a class of combinatorial patterns that appear
in an input data satisfying a specified constraint, and it is a central task in computational
biology, temporal sequence analysis, sequence and text mining [3]. We consider the patterndiscovery problem for the class of patterns with wild cards, which are strings consistingof constant symbols (called solid letters) drawn from an alphabet and variables ’◦’ (calledwild cards) that matches any symbol [8, 12]. For instance, B◦AB and B◦AB◦◦B are examplesof patterns. Given a positive integer θ called quorum, a frequent motif (or motif , for short)in an input string s is a pattern that appears at least θ times in s.
Frequent motif discovery has a drawback that a huge number of motifs are often
generated from an input string without conveying any useful information. To overcome
this problem, we focus on discovery of maximal motifs [8]. The semantics of a pattern x is
given by the location list L(x) consisting of the positions in s at which the pattern occurs.
A motif is said to be maximal if it is not properly contained by other motifs with theequivalent location lists allowing position shift. In Fig. 1, we show all maximal motifs andall motifs with θ = 3 on input sting s = ABBCABRABRABCABABRABBC and quorum θ = 3.
For example, the pattern R ◦ B with location list {6, 9, 17} is a motif but not maximal since
there is another motif ABRAB with location list {4, 7, 15} obtained from {6, 9, 17} by shifting
leftward with 2. In this example, we can also observe that there are only 10 maximal motifs
among 50 motifs. In general, the number of maximal motifs can be exponentially smaller
than the number of motifs. while the former is exponential in the input size.
In this paper, we study the problem of enumerating all maximal motifs in an input
string of length n. In particular, from practical viewpoint, we are interested in thosealgorithms that have small space and delay complexities independent from the output sizein addition to polynomial amortized time per motif. However, the output-polynomial timecomputability for maximal motif discovery with polynomial space and delay is still open.
First we show exponential lower bound and succinctness results on the number ofmaximal motifs, which show the limit of a straightforward approach. By examining theprevious approaches [8, 12, 11], we present a simple output-polynomial time algorithm for
maximal motif enumeration by breadth-first search, which possibly requires exponential
space and delay. Then, we present an efficient algorithm that enumerates all maximal
motifs in an input string of length n with O(n3 ) time per motif with O(n2 ) space andO(n3 ) delay. A key of the algorithm is depth-first search on a tree-shaped search route for all
maximal motifs build by prefix-preserving closure extension, which enable us to enumerate
all maximal motifs without storing discovered motifs for duplication and maximality tests.
To the best of our knowledge, this is the first result on a polynomial space polynomial
delay algorithm for maximal pattern discovery for sequences.
The organization of this paper is as follows. In Section 2, we give definitions andbasic results. In Section 3 gives lower bound results on the number of maximal motifs.
In Section 4, we prepare tools for studying maximal motifs. In Section 5, we review theprevious results on maximal motif enumeration. In Section 6, we present our algorithm
MaxMotif that enumerates all maximal motifs with polynomial space and polynomial
delay from an input string. In Section 7, we conclude this paper.

2

Preliminaries

2.1

Maximal Motifs

We briefly introduce basic definitions and results on maximal pattern enumeration according to [12, 11]. We denote the set of all integers by Z. Given an alphabet ∆, a string
over ∆ is a consecutive sequence of letters s = a[0] · · · a[n − 1] ∈ ∆∗ , where n ≥ 0 anda[i] ∈ ∆ for every 0 ≤ i ≤ n − 1. The length of s is |s| = n and the empty string is thestring ε of length 0. If s = uvw for some u, v, w ∈ ∆∗ , then we say that u is a prefix , v is a
substring, and w is a suffix of s. For every 0 ≤ i ≤ j ≤ n − 1, s[i..j] denotes the substring
1

00
10
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

ABBCABRABRABCABABRABBC
[]*
[B]*
[AB]*
[BC]*
[ABRAB]*[BoAB]*[ABoAB]*[BoABoAB]*[BoooooB]*[BoABoooooB]*

21
9
7
3
3
5
4
3
4
3

[]*
21
[B]*
9
[AB]*
7
[A]
7
[BC]*
3
[C]
3
[ABRAB]* 3
[R]
3
[RA]
3
[RAB]
3

input string squorum θ = 3[AooA]
4[BRA]
3[BRAB]
3[BRoB]
3[BoAB]* 5[BooB]
5[ABoAB]* 4[ABooB] 4[AooAB] 4[AoooB] 4[RoB] 3[BR]
3[ABR] 3
[ABRA] 3[ABRoB] 3[ABoA] 4[AoR] 3
[AoRA] 3[AoRAB] 3[AoRoB] 3

10 maximal motifs[BoA]
5[BoABoA] 3[BoAooA] 3[BooBoA] 3[BooooA] 3[BoABoAB]*3[BoABooB] 3[BoAooAB] 3[BoAoooB] 3[BooBoAB] 3[BooBooB]
3[BooooAB]
3[ABoooooB]
3[BoooooB]*
4[BoABoooooB]* 3[AooooooB]
3[BoAooooooB] 3[BooBoooooB] 3[BooooooooB] 3

50 motifs (frequent motifs)

Fig. 1. Examples of maximal motifs (left) and motifs (right) for an input string s and a quorum θ, where* indicates a maximal motif and the number associated to each motif indicates its frequency. These 10
maximal motifs are representatives containing the whole information on the occurrences of all motifs in s.

ai ai+1 ·P· · aj . For a set S ⊆ ∆∗ of strings, we denote by |S| the cardinality of S and by||S|| = s∈S |s| the total length of S.
Let Σ be an alphabet of solid characters (or constant letters). Let ◦ 6∈ Σ be a distinguished letter not belonging to Σ, called the wild card (or don’t care). A wild card
◦ matches any solid character c ∈ Σ and also matches ◦ itself. An input string is astring s ∈ Σ ∗ of solid characters. In what follows, we fix an arbitrary input strings = s[1] · · · s[n] ∈ Σ ∗ of length n ≥ 1.
Definition 1 (pattern [8, 12, 11]). A pattern over Σ is a string x in Σ (Σ ∪ {◦})∗ Σthat starts and ends with a solid character, or an empty string ε.
We denote the class of patterns by P = {ε} ∪ Σ ∪ (Σ ·(Σ ∪ {◦})∗ ·Σ). For example,
ABC and B ◦ C are patterns, but ◦BC and ◦ ◦ B◦ are not. Note that ε is a pattern in our
definition. We define a binary relation ¹ over letters and patterns, called the specificity
relation 3 . For letters a, b ∈ Σ ∪ {◦}, we define a ¹ b if either a = b or a = ◦ holds.
Definition 3 (occurrence [8, 12, 11]). For patterns x and y, We say that x occurs at
position p in y if there exists some index 0 ≤ p ≤ |y| − |x| such that for every index
0 ≤ i ≤ |x| − 1, x[i] ¹ y[p + i] holds. The empty pattern ε occurs at any 0 ≤ p ≤ n − 1.
Then, we also say that p is an occurrence of x in y, and that x matches the substringy[p..p + |x| − 1].
Example 1. Pattern x = B ◦ D occurs in pattern y = AB ◦ DA at position 1, and x occurs
three times in string s = EABCDABEDBCDE at positions 2, 6 and 9.
We extend binary relation ¹ from letters to patterns as follows. For patterns x and yin Σ (Σ ∪ {◦})∗ Σ, if x occurs at some position p in y, then we define x ¹ y and say thateither x is contained by y or y is more specific to x. For any pattern x, we define ε ¹ x. If
x ¹ y but y 6¹ x, then we define x ≺ y and say that either x is properly contained by y or
y is properly more specific to x. We can see that if x ¹ y and y ¹ x hold, then x and y are
identical each other. Furthermore, ¹ is a partial order over patterns in Σ (Σ ∪ {◦})∗ Σ. A
maximal motif y is a successor of maximal motif x (within M) if x ≺ y and there is no
maximal motif z such that x ≺ z ≺ y. A location list is any subset L ⊆ {0, . . . , n − 1}.
Definition 4 (location list [8, 12, 11]). For an input string s ∈ Σ ∗ of length n ≥ 0, thelocation list of pattern x is the set L(x) ⊆ {0, . . . , n − 1} of all the positions on s at which
x occurs. The cardinality |L(x)| is called the frequency of x on s.
Example 2. Consider the input string s = EABCDABEDBCDE over Σ = {A, B, C, D, E}. Then,the location list of pattern x = B ◦ D in s is L(x) = {2, 6, 9}.
Lemma 1. For any motifs x and y, the following properties hold.
3

The binary relation ¹ is also called the generalization relation or the subsumption relation in artificial
intelligence and data mining.

21. If x ¹ y then L(y) ⊆ L(x) + d for some nonnegative integer d.
2. If x ≺ y then |L(x)| > |L(y)| and |x|Σ < |y|Σ hold, where |x|Σ is the number of solid
letters in x.
The converse of properties 1 and 2 of Lemma 1 does not hold in general. A minimum
frequency threshold, or quorum, is any positive number θ ≥ 1. Let θ ≥ 1 be a quorum.
We say that pattern x is a θ-motif (or motif , for short) in s if |L(x)| ≥ θ holds [8, 12,
11].
Let L be any location list and d be any integer. Then, we define the shift of L withdisplacement d by L + d = { ` + d | ` ∈ L }. We write L − x to represent the set L + y withy = −x.
Definition 6 (Parida et al [8]). Let θ ≥ 1 be a quorum. A motif x is maximal in s if
for any motif y that properly contains x, there is no integer d such that L(y) = L(x) + d.
In other words, θ-motif x is maximal in s iff there exists no θ-motif in s properly
containing x that is equivalent to x under shift-invariance.
Example 3. Let s = EABCDABEDABCDE over Σ = {A, B, C, D, E} be an input string. Consider
motifs x = AB ◦ D with location list L(x) = {1, 5, 8}, y = B ◦ D with L(y) = {2, 6, 9}, andz = D with L(z) = {4, 8, 11}. We can see that z ≺ y ≺ z holds and x, y, z are equivalenteach other. For instance, L(z) = L(x)+d with the displacement d = 3. Then, x is maximal
in s, but y and z are not.
Now, we state our problem as follows.
Definition 7. The maximal motif enumeration problem is, given an input string s oflength n and a quorum θ ≥ 1, to enumerate all maximal motifs in s without repetition.

2.2

Enumeration algorithms

We introduce terminology for enumeration algorithms according to [7, 14]. An enumeration
algorithm for an enumeration problem Π is an algorithm A that receives an instance I of
Π and produces all solutions S in the answer set S(I) of Π, e.g., maximal motifs in our
problem, into a write-only output stream O in which each solution appears exactly once.
Let A be an enumeration algorithm, N = ||I|| and M = |S(I)| be the input and theoutput sizes on I, p(N ), q(N, M ) be polynomials. A is of output-polynomial (P-OUTPUT)
if the total running time of A for all solutions is bounded by a polynomial q(N, M ). A is ofpolynomial enumeration time (P-ENUM) if the amortized time for each solution x ∈ S isbounded by a polynomial p(N ). That is, the total running time is linear, M · p(N ), in the
output size M . A is of polynomial delay (P-DELAY) or exact polynomial enumeration time
if the delay, which is the maximum computation time between two consecutive outputs, isbounded by a polynomial p(N ) in the input size N . A is of polynomial space (P-SPACE) if
the maximum size of its working space, without the size of output stream O, is bounded bya polynomial p(N ). We often call A in P-ENUM and P-DELAY, respectively, a polynomial
time enumeration algorithm and an exact polynomial time enumeration algorithm. By
definition, P-OUTPUT is weakest and P-DELAY is strongest among P-OUTPUT, PENUM, and P-DELAY.

3

Lower bounds for the number of maximum motifs

We show the following lower bound of the number of maximal motifs in a given sequence,
which justifies output-sensitive algorithms for the maximal motif enumeration problem.
The upper bound of |Mθ | is obviously 2O(N ) .
Theorem 1 (exponential lowerbound of maximal motifs). There is an infinite series of input strings s0 , s1 , s2 , . . . , such that for every i = 0, 1, 2, . . ., the number |M| ofmaximal motifs in si is bounded below by 2Ω(N ) , that is, exponential in N = |si |.
3

Proof: We show a sketch of the proof. Let Σ = {#, 0, 1} and n ≥ 1 be any nonnegative
integer. Let s = #t1 # · · · #tn # over Σ be the input string corresponding a boolean matrix
with 1’s on the diagonal, where each block ti = b1 · · · bn ∈ {0, 1}n (1 ≤ i ≤ n) is definedas: bj = 1 if i = j and bj = 0 otherwise for every j = 1, . . . , n. Next, we define the set
X of patterns consisting of all patterns of the form x = #p1 . . . pn # ∈ {#} · {0, ◦}n · {#},
which represents a bit vector of length n with ◦ as on and 0 as off bits. Then, we can showthat Lx contains the position of i-th block ti iff pi is ◦ (on bit). This means that all of 2npatterns have mutually distinct location lists, and thus,Pthey¡aremaximal in s if |Lx | ≥ θ.
n¢n
1
If θ = 2 n then the size |X ∩ M| is bounded below by k=θ k = 2Ω(n) .
2
The following theorem says that the number of motifs can be exponentially larger than
the number of maximal motifs.
Theorem 2 (succinctness of maximal motifs). There is an infinite series of input
strings s0 , s1 , s2 , . . . , such that for every i ≥ 0 with quorum θ = 12 N , the number F = |F|of motifs in si is exponential (more precisely 2Ω(N ) ) in the input size N , while the number
M = |M| of maximal motifs in si is linear in N , where N = |si |.
See Section A of Appendix for the proof of the above theorem. From Theorem 2, weknow that a straightforward algorithm for M based on enumeration of motifs does notwork efficiently. This is also true for most real world datasets. Fig. 1 shows an example,
where there are only 10 maximal motifs among 50 motifs in a string of length 21.

4

Merge and Closure

In this section, we introduce two operations, called merge and closure, for studying maximal motifs [1, 3, 12, 11]. We start with technical definitions.
For alphabet ∆, we denote by ∆∞ the class of infinite strings, which are functions of
the form α : Z → ∆. For a string x of length m ≥ 0, we define its infinite version (orexpanded version) bxc as an infinite string bxc ∈ (Σ ∪ {◦})∞ such that for every integer i,
bxc[i] = x[i] if index i is defined, i.e., 0 ≤ i ≤ n − 1, and bxc[i] = ◦ otherwise. Conversely,
for infinite string x ∈ (Σ ∪ {◦})∞ , its finite string version (or trimmed version) is thefinite string dxe ∈ {ε} ∪ Σ ∪ (Σ · (Σ ∪ {◦})∗ · Σ) obtained from x by taking the longest
substring that starts and ends with a solid character. If x contains no solid character, dxe
is not defined. By definition, if x is a pattern then dbxce = x for every finite x, but it is
not the case for general string such as x = ◦ B ◦ C ◦.
For infinite string x and integer d, we define the shift of x with displacement d by theinfinite string (x + d) such that (x + d)[i] = x[i − d] for every integer i.
Definition 8 (shift). For finite string x and integer d, the shift of x by displacement d
is an infinite string (x + d) = bxc + d.
Example 4. Given a finite string s = EABCDABED, its infinite version is bsc = · · ·◦◦ ↓ EABCDABED◦◦ · · ·, where ↓ indicates the position of origin i = 0. With displacement d = 2, the shiftof bsc is (bsc + 2) = · · · ◦ ◦ EA ↓ BCDABED ◦ ◦ · · ·. Again, its finite version is d(bsc + 2)e =EABCDABED = s, where ↓ is eliminated.

4.1

Merge of infinite and finite strings.

Next, we define the merge operator ⊕. For letters a, b ∈ Σ, we define a ⊕ a = a anda ⊕ ◦ = ◦ ⊕ a = a ⊕ b = ◦ if a 6= b. For infinite strings α, β, the merge of α and β, denotedby α ⊕ β, is the infinite string such that (α ⊕ β)[i] = α[i] ⊕ β[i] for every integer i. For
finite strings x, y, the merge of α and β, denoted by x ⊕ y, as the finite string or patternx ⊕ y = d bxc ⊕ byc e.
Let X = {α1 , . . . , αk } be any set of possibly
infinite L
strings. Since ⊕ is associative andLcommutative, we denote by α1 ⊕ · · · ⊕ αk = ki=1 αi = X pairwise applications of ⊕ toall elements of X from left to right.
4◦◦◦◦◦◦AB↓BCABRABRABCABABRABBC s − 2◦◦◦ABBCA↓BRABRABCABABRABBC◦◦◦ s − 5
ABBCABRA↓BRABCABABRABBC◦◦◦◦◦◦ s − 8◦◦◦◦◦◦◦◦↓B◦AB◦AB◦◦◦◦◦◦◦◦◦◦◦◦◦ (s − 2) ⊕ (s − 5) ⊕ (s − 8)B◦AB◦ABd(s − 2) ⊕ (s − 5) ⊕ (s − 8)e = Clo(x)Fig. 2. Computing the closure Clo(x) of pattern x = B ◦ AB in input string s = ABBCABRABRABCABABRABBC.

Definition 10 (merge of location list [3, 11]). Let s be an input string s and L ={d , . . . , dk } ⊆ {0, . . . , n − 1} beLany location
list on s.LThen, the merge of L, denoted by
L1Lk
L, is defined by the pattern
L = ki=1 (s
+
d
)
if
i
i=1 (s + di ) is finite, i.e., it startsLand ends with a solid character. Otherwise,
L is the empty string ε.
0 be any location lists. Then, the following (1) and (2) hold: (1) If
Lemma 4. Let
L, LL
L 0
L
L
0
L ⊆ L then
L ¹ L. (2)L = (L + d) for any integer d.

Definition 11 (closure L
operation [11, 12]). Given a pattern x, the closure 4 of x on
s is the pattern Clo(x) = L(x).
Example 5. In Fig. 2, we show an example computation of the closure of pattern x = B ◦ A
with L(x) = {2, 5, 8} on input string s = ABBCABRABRABCABABRABBC, where indices startfrom zero. We first shift s leftward for each position d of x. This operation sets the origin↓ of s to each occurrence d. Then, we take the merge t = (s − 2) ⊕ (s − 5) ⊕ (s − 8) byfinding a common solid letter in each column one by one. Finally, we obtain the closureClo(x) = dte = B ◦ AB ◦ AB by trimming the resulting string.
Lemma 6. Clo(x) is always defined, unique, and computable in O(n|L(x)|) time given
motif x, its location list L(x), and input string s of length n.
Lemma 7 (properties of closure). Let x, y be any patterns occurring in s and X, Y be
any location lists.
1. x ¹ Clo(x).
2. L(x) + d = L(Clo(x)) for some integer d ∈ Z.
3. Clo(x) = Clo(Clo(x)).
4. If x ¹ y then Clo(x) ¹ Clo(y).
5. Clo(x) is the unique maximal element w.r.t ¹ in the equivalence class of patterns[x] = { y | L(x) = L(y) + d for some d ∈ Z } containing x.
Theorem 4 (characterization of maximal motifs [11]). For any motif x in s, x is
maximal in s iff Clo(x) = x holds.
Theorem 5. Let x, y ∈ M be maximal motifs. Then, x ¹ y iff L(x) + d ⊇ Ly for some
integer d. Furthermore, x = y iff L(x) + d = L(y) for some integer d.
Proof: The theorem immediately follows from Theorem 4.
25Previous approaches for maximal motif enumeration

We give a brief review on possible approaches for output-sensitive computation of M andsummarize the previous results.

5.1

Frequent pattern generation.

A most straightforward method of generating maximal motifs is to enumerate all motifs
in s, classify them into equivalence classes according to their location lists, and find the
maximal motifs for each equivalence class. This method requires O(|F|) time and O(||F||)memory. Since O(|F|) can be exponentially larger than |M|, we cannot obtain any outputsensitive algorithm in time and memory.
4

L

The closure operation
L(x) for motifs was introduced in [11] and called the maximal extension in[12]. The set-counterpart of the closure has been known in data mining [10, 15].

5

Algorithm MaxBasis( θ: quorum, s: input string, B: basis)
1 M0 := B; i := 02 while (∆ 6= ∅) do begin3∆ := ∅;
4foreach y ∈ Mi and d ∈ {0, . . . , n − 1} do
Si
5
if y ⊕ (s + d) 6∈ ( k=0 Mk ∪ ∆) then ∆ = ∆ ∪ {y ⊕ (s + d)}; output x;6
Mi+1 := ∆; i := i + 1;
7 end

Fig. 3. An polynomial time enumeration algorithm for generating M from B based on breadth-first search.
This algorithm does not have polynomial space or polynomial delay.

5.2

Using the basis of motifs.

Parida et al [8] introduced the use of the basis for maximal motif enumeration. A basis
for M is a subset B ⊆ M of motifs such that M can be generated by finite applicationsof an operation, e.g., ⊕, over M. Parida et al. [8] defined the basis BI of irredundant
motifs. Pisanti et al. [12] introduced the basis BT of tiling motifs. A maximal motif istiling if S
for any maximal motifs y1 , . . . , yk and any integers d1 , . . . , dk with x ¹ yi , if
L(x) = i L(yi ) then x = yi for some i. Pelfrêne et al [11] introduced the basis BP ofprimitive motifs. Pisanti et al. [13] propose a simple method for generating M from BT byiteratively computing the merge x = y ⊕ (z + d) for all possible maximal motifs y, z ∈ M
generated so far and all displacements d with explicit check of duplication. This method
requires O(|M|2 · n) total time and O(||M||) space given BT . Since the total time is not
linear in |M|, it does not have amortized polynomial enumeration time per motif while it
has output-polynomial time.

5.3

An improved method with using the basis.

We can improve Pisanti et al.’s method for M adopting an idea used in [11] for generationof BP (and BT ) from s. Fig. 3 shows our algorithm MaxBasis that computes M from BT
based on the next lemma:
Lemma 8 (generation of maxmal motifs from the basis). Let θ ≥ 1 be a quorum.
Any maximal motif x ∈ M satisfies either (i) x ∈ BT , or (ii) there exist some y ∈ M andsome integer d such that x ≺ y and x = y ⊕ (s + d).
Theorem 6. Given a quorum θ ≥ 1, an input string s of length n, and the basis BT oftiling motifs, the algorithm MaxBasis in Fig. 3 enumerates all maximal motifs of M from
B in O(n2 ) amortized time per motif with O(||M||) space.
Here, we are given BT and |BT | ≤ |M|. We use a trie to store Mi and ∆ for O(|x|)
membership of pattern x. Since the total time is O(|M| · n2 ), linear in the output size,
MaxBasis has polynomial amortized time per motif. However, its space complexity anddelay are O(||M||) and O(|MT | · n2 ), respectively, in the worst case. Thus, MaxBasis is
not a polynomial space polynomial delay algorithm even given the basis BT as input.
Note that it is still open whether the basis BT (or BP ) is output-polynomial timecomputable from s [12, 13, 11]. For every integer i ≥ 1, let us denote the basis for quorum i
by BTi . The total running time of the algorithms in [11] and [13] are only bounded byPO(nθ θi=1 |BTi |) or nO(θ) , which may not be O(|BT |) = O(|BTθ |). Hence, it seems difficult
to obtain output-polynomial time algorithm for BT and thus M in this approach. 55Parida et al. [9] presented an output-polynomial time algorithm for the class of flexible motifs, andclaimed that they also presented a similar algorithm for maximal motifs with wild cards in [8]. Since
these algorithms seem to depend on an unproved conjecture in [8], however, we did not include them. At
least, the algorithm in [9] requires the space and the delay proportional to the output size |M|. Thus,
it is not polynomial space and polynomial delay.

6

6

A polynomial space polynomial delay algorithm using depthfirst search

In this section, we present an efficient depth-first search algorithm MaxMotif that, given
a quorum θ ≥ 1 and an input string s of length n, enumerates all maximal motifs x in s
in O(|L(x)| · n2 ) delay and O(|L(x)| · |x|) space in the input size n. In what follows, we fix
input string s of length n ≥ 1 and 1 ≤ θ ≤ n.

6.1

Building tree-shaped search route for maximal motifs

Our algorithm MaxMotif in Fig. 5 computes all maximal motifs in exactly O(n3 ) time
per motif, thus with O(n3 ) delay, and with O(n2 ) space using depth-first search over M,
which enables us to avoid the use of extra storage for keeping all discovered motifs. We
explain the details of the algorithm in the following sections.
We first build a tree-shaped search route T = (V, P, ⊥) for traversing all maximal
patterns (Fig. 4). The node set V = M consists of all maximal motifs of M, P is the setof reverse edges defined later, and ⊥ = Clo(ε) is the root motif called the bottom motif .
Lemma 9. ⊥ = Clo(ε) is the unique shortest maximal motif in s.
Proof: Clearly, L(Clo(ε)) = L(ε) is the largest location list {0, . . . , n − 1}. Thus it follows
from Lemma 5 that Clo(ε) ¹ x for any maximal motif x.
2
If s contains at least two solid letters then ⊥ = ε, otherwise ⊥ = a for the only lettera in s. Next, we define the set P of reverse edges from a child to its parent as follows.
Given a maximal motif x, the core index of x, denoted by core i(x), is the smallest index
0 ≤ ` ≤ |x| − 1 such that L(x) = L(y) for the prefix y = x[0..`].
Then, we assign the unique parent to each non-bottom maximal motifs.
Definition 12 (parent of maximal motif ). Let y be a maximal motif such that y 6= ⊥and ` = core i(y) be the core index of x. Then, the parent of y, denoted by P(y), is thepattern P(y) = Clo(dy[0..` − 1]e). 6
Lemma 10. For every maximal motif x such that x 6= ⊥, P(x) is always exists, unique,and maximal. Furthermore, P(x) ≺ x holds.
Proof: Let p = dy[0..` − 1]e. If y 6= ⊥, then ` − 1 = core i(y) − 1 ≥ −1 and p is always
defined. Since p ¹ y and L(y) 6= ∅, L(p) ⊇ L(y) 6= ∅. From Theorem 4, P = Clo(p) is
uniquely defined and maximal. if ` is the core index of y, L(p) ⊃ L(y). Since both of x, y
are maximal, it follows from Lemma 4 and Theorem 5 that x = Clo(p) ≺ Clo(y) = y. 2
Lemma 11. The relation ¹ is acyclic on M, i.e., there is no infinite decreasing chain
x0 Â x1 Â · · · Â xi Â · · · , i ≥ 0, of maximal motifs of M.
Theorem 7. T = (V, P, ⊥) is a spanning tree for all maximal motifs in M.
The remaining task is to show how to enumerate all children y of a given parent motif
x without using extra space, which is not an easy task since we have only reverse edges.
We discuss this issue in the next subsection.

6.2

Prefix-preserving closure extension

We introduce the prefix-preserving closure extension defined as follows. A substitution for
motif x is a pair ξ = hk ← ci ∈ Z × Σ of integer k and solid letter c. If x[k] = ◦, ξ iscompatible to x. The application of ξ to x is the motif xξ = xhk ← ci defined as follows.
For finite string x with index k inside the string, i.e., 0 ≤ i ≤ |x| − 1, we define xξ as
6

In the definition, y[0..` − 1] ∈ Σ(Σ ∪ {◦})∗ ∪ {ε} may not be a proper pattern. Thus, we use dy[0..` − 1]einstead of y[0..` − 1] to remove the trailing ◦’s.

7

input string s

00
10
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

quorum θ = 3

ABBCABRABRABCABABRABBC

pattern lattice L = (M, ≤) for maximal motifs

spanning tree T = (M, P) for maximal motifs
ε

21

<0,A>

AB

AB

7

<2,R>

ABRAB

3

ABoAB

4

BC

3

<3,A>
<0,B>

B

9

ε

21

<1,C>
<2,A>

BoAB
<5,A>
<9,B>

<6,B>

BoooooB

5
BoABoAB3

BoABoooooB

3

B

ABRAB

3

ABoAB

4

BC

3

BoAB

5

7

9
BoooooB

4

BoABoAB3

BoABoooooB

3

4

Fig. 4. The spanning tree T = (M, P) (left) and the pattern lattice L = (M, ¹) (right) for maximal
motifs of M on quorum θ = 3 and input string s (top). Each box represents maximal motif x in M andthe number right to the box indicates its frequency |L(x)|. Each arrow indicates ordering, P or ¹, of atree/lattice. (Sec. 6.1). An arrow in the tree T indicates the ppc-extension with seed hk, ci. The newly
introduced letter c is written in bold face. (Sec. 6.2). There are 10 maximal motifs among 49 motifs in s.

follows (ξ is called replacement): for every index i, xξ[i] = c if i = k and xξ[i] = x[i]otherwise. For infinite string x, we define xξ in the same way. For finite string x with theindex k outside the string, i.e., k > |x| − 1 or k < 0 (ξ is called right extension or left
extension), we define xξ = dbxcξe. For example, if x = BA ◦ B, then xh−1 ← Ci = CBA ◦ B,
xh2 ← Ci = BACB, and xh6 ← Ci = BA ◦ B ◦ ◦ C.
Definition 13 (ppc-extension). For any maximal motifs x, y such that y 6= ⊥, a motif
y is a prefix-preserving closure expansion (or a ppc-extension) of x if the following (i)–(iii)hold:(i) y = Clo(xhk ← ci) for some substitution, called the seed , ξ = hk ← ci ∈ Z × Σ
compatible to x, that is, y is obtained by first substituting c at index i and then taking
its closure,(ii) the index k satisfies k > core i(x), and(iii) x[0..k − 1] = y[0..k − 1], that is, the prefix of length i − 1 is preserved, where x[0..k − 1]is the string bxc[0..k − 1] obtained from x by padding trailing ◦’s if necessary.
Example 6. In Fig. 4, we show an example of the spanning tree for M generated by the
ppc-extension, where quorum is θ = 3 and input string is s = ABBCABRABRABCABABRABBC.
We have maximal motif x = AB with location list L(x) = {0, 4, 7, 10, 15, 18}. If we apply
substitutions ξ = h2, Ri and ξ = h3, Ai to x then we obtain the ppc-extension y = ABRAB =Clo(ABR) with {4, 7, 15}, and z = AB ◦ AB = Clo(AB ◦ A) with {4, 7, 10, 15}, respectively.
The following theorem is the main result of this section. For the proof, please see
Section B of Appendix.
Theorem 8 (correctness of ppc-extension). For any maximal motifs x, y such thaty 6= ⊥. Then, (i) x = P(y) if and only if (ii) y = Clo(xξ) is a prefix-preserving closure
expansion of x for some substitution ξ = hk ← ci ∈ Z × Σ compatible to x. Furthermore,
there exists exactly one ξ satisfying condition (ii) for each y.

6.3

A polynomial space polynomial delay algorithm

Based on Theorem 8, we present in Fig. 5 our algorithm MaxMotif that enumerates
all maximal motif in a given input string by the depth-first search over M applying the
ppc-extension to each maximal motifs.
8

Algorithm MaxMotif(θ: quorum, s: input string)
1 Expand(⊥, θ, s);Procedure Expand(x: motif, θ: quorum, s: input string)
2 if |L(x)| < θ then return;3 output x;
4 for k := core i(x) + 1 to |s| do5foreach c ∈ Σ do begin
6
y = Clo(xhk ← ci);7
if x[0..k − 1] = y[0..k − 1] then8call Expand(y, s, θ);9end forFig. 5. A polynomial space polynomial delay enumeration algorithm for M.

A straightforward implementation of the procedure Expand in Fig. 5 requires O(|L(x)|·n) time for each of n · |Σ| possible children at line 4 to line 9 even when none of themsatisfies the quorum θ. This only yields an algorithm with O(|Σ| · |L(x)| · n2 ) = O(|Σ|n3 )time and delay. Then, we have the following theorem.
Theorem 9. Given a quorum θ ≥ 1 and an input string s of length n, the algorithm
MaxMotif in Fig. 5 enumerates all maximal motifs x of M in O(|L(x)| · n2 ) amortized
time per motif with O(|L(x)| · |x|) space and O(|L(x)| · n2 ) delay.
Proof: By Theorem 7 and Theorem 8, we see that the algorithm MaxMotif visits all
maximal motifs on the spanning tree T starting from the root ⊥. Since T is a tree andany maximal motif appears in T , the algorithm enumerate M without duplicates.
Now, we estimate the work time W (x) at line 2 and at line 4 to line 8 for each parent
maximal motif x as follows. For each x, its location list L(x) at line 2 and its its closureClo(x) at line 6 can be computed in O(|L(x)| · n) time. By Lemma 15, if x is obtained
from its parent p by ppc-extension with seed hk, ci, then core i(x) = k, and this can becomputed in O(1) time at line 4 by keeping k. Thus, a straightforward implementation,requires the total computation time O(|Σ| · |Lx | · n) at line 5 to line 8.
To reduce computation time further, we replace line 5 to line 8 by the following procedure OccurrenceDeliver 7 that computes y = Clo(xhk ← ci) and L(y) for all solid
letterc such that L(y) 6= ∅ during a single scanning on L(x). Its total running time isPO( c∈Σ 0 |L(c)| · n) = O(|L(x)| · n) time.
OccurrenceDeliver ≡1 Initialize all L(c) := ∅ for all c ∈ Σ 0 , and then Σ 0 := ∅;2 foreach d ∈ L(x) do
3
L(c) := L(c) ∪ {d} and Σ 0 = Σ 0 ∪ {c}, where c := s[d + k];
5 foreach c ∈ Σ 0 do
6Compute y = Clo(xhk ← ci) using L(c)This yields the work W (x) = O(|L(x)| · n2 ) instead of O(|Σ| · |L(x)| · n2 ). From this, thedelay is W (x)·|x| time since the depth of T is Θ(|x|). Next, we reduce the delay W (x)·|x| toW (x) using a technique by Uno [14] that transforms any tree-search enumeration algorithmwith work time W (x) at each node into a W (x) delay enumeration algorithm by changing
the timing of output alternatively according to the parity of the depth of x. For details,
please consult [14]. The space complexity is obviously O(|L(x)| · |x|) since each recursive
call has |x| ancestors.
2
7

Occurrence deliver is introduced for closed itemsets enumeration in Uno et al. [15]9In summary, MaxMotif computes all maximal motifs in O(n3 ) time per motif with
O(n2 ) space and O(n3 ) delay in the input size n.
Corollary 10 The maximal motif enumeration problem is solvable in polynomial spaceand polynomial delay in the input size n = |s|.

7

Conclusion

In this paper, we presented a polynomial space polynomial delay algorithm for enumerating
all maximal motifs in an input string for the class of motifs with wild cards. By the use of
depth-first search realized by the prefix-preserving expansion technique we introduced, thealgorithm enumerate all motifs in the unique way without explicitly storing and checking
the motifs enumerated so far. This method drastically improves the space and the delay
complexities of the previous output-polynomial time algorithms based on breadth-firstsearch.
In data mining, maximal motifs for sets are called closed itemsets [10]. There are anumber of closed itemset discovery algorithms for closed itemsets [5, 10], while only a
few algorithms are known for closed sequences and closed trees [3, 15, 16]. We extend the
ppc-extension, which is originally introduced for closed itemsets, for maixmal sequences.
Thus, the result of this paper will be a first step towards efficient enumeration of maximal
patterns for complex combinatorial objects such as sequences, trees, and graphs.
Pattern discovery for classes of unions of patterns is one of the difficult problems inmachine learning. Since the class of maximal motifs is a class of unions generated fromtiling motifs [12], it will be a future problem to extend the proposed enumeration method topattern discovery for unions of sequence patterns, e.g. [4]. Implementation of the proposed
algorithm with practical improvement and evaluation of the algorithm on the real world
datasets, e.g., biological datasets, are also interesting future problems.

References
1. A. Apostolico and L. Parida, Compression and the wheel of fortune, In Proc. the 2003 Data Compression Conference (DCC’03), IEEE, 2003.
2. H. Arimura, T. Uno, A Polynomial Space Polynomial Delay Algorithm for Enumeration of Maximal
Motifs in a Sequence, Technical Report TCS-TR-A-05-6, Division of Computer Science , Hokkaido
Univeristy, July 2005.
3. H. Arimura, T. Uno, An Output-Polynomial Time Algorithm for Mining Frequent Closed Attribute
Trees, In Proc. Inductive Logic Programming, LNAI 3625, Springer, 1–19, August 2005. (to appear)
4. H. Arimura, T. Shinohara, S. Otsuki, Finding minimal generalizations for unions of pattern languages
and its application to inductive inference from positive data, In STACS’94, LNCS 775, Springer-Verlag,
649–660, 1994.
5. E. Boros V. Gurvich, L. Khachiyan, K. Makino, The complexity of generating maximal frequent andminimal infrequent sets, In Proc. STACS ’02, LNCS, 133-141, 2002.
6. M. Crochemore and W. Rytter, Jewels of Stringology, World Scientific, 2002.
7. L. A. Goldberg, Polynomial space polynomial delay algorithms for listing families of graphs, In
Proc. the 25th STOC, ACM, 218–225, 1993.
8. L. Parida, I. Rigoutsos, A. Floratos, D. Platt, and Y. Gao, Pattern discovery on character sets and realvalued data: linear bound on irredundant motifs and effcient polynomial time algorithm, In Proc. the11th SIAM Symposium on Discrete Algorithms (SODA’00), 297–308, 2000.
9. L. Parida et al., An output-sensitive algorithm for ..., In Proc. the 12th International Conference on
Combinatorial Pattern Matching (CPM’01), LNCS 2089, 131–142, 2001.
10. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering Frequent Closed Itemsets for Association
Rules, In Proc. ICDT’99, 398–416, 1999.
11. J. Pelfrêne, S. Abdedda¨m, and J. Alexandre, Extending Approximate Patterns, In Proc. CPM’03,
LNCS 2676, 328–347, 2003.
12. N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot, A basis of tiling motifs for generating repeatedpatterns and its complexity for higher quorum, In Proc. MFCS’03, LNCS 2747, 622–631, 2003.
13. N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot, A comparative study of bases for motif
inference, In String Algorithmics, C. Iliopoulos and T. Lecroq editors, KCL publications, 2004.
14. T. Uno, Two General Methods to Reduce Delay and Change of Enumeration Algorithms, NII Technical
Report, NII-2003-004E, April 2003.

10

15. T. Uno, T. Asai, Y. Uchida, H. Arimura, An efficient algorithm for enumerating closed patterns intransaction databases, In Proc. DS’04, LNAI 3245, Springer-Verlag, 16-30, 2004.
16. X. Yan, J. Han, CloseGraph: Mining Closed Frequent Graph Patterns In Proc. SIGKDD’03, 2003.

11

Appendix
This appendix is not included in the submission and can be ignored

A

Proof of Theorem 2

Lemma 3 (transformation from closed itemsets to maximal motifs). For everytransaction database r = {t1 , . . . , tm } consisting of m transactions over n items of total
size N = mn, there exists an input sequence s of length O(N + m2 ) such that the numberMθr of θ-frequent closed itemsets in r equals to the number Mθs of maximal motifs in s.
Proof: (Sketch) Given items I = {1, . . . , n} and a transaction database r = {t1 , . . . , tm },Σ = { aj , bij , #ij | a ∈ I, 1 ≤ i ≤ m, 1 ≤ j ≤ n } ∪ {#} is an alphabet for s. The letters
aj , bij , and #ij , resp., stand for items, blanks, and delimiters. We define the input strings = s1 w1 · · · sn−1 wn−1 sn wn over Σ of length N = mn + 21 m2 . For every i = 1, . . . , n, let ti
be the i-th transaction of r. Then, the block si is defined by si = x1 · · · xn such that forevery j = 1, . . . , n, xj = aj if j ∈ ti and xj = bij if j 6∈ ti . The delimiter wi is defined bywi = y1 · · · yi such that yj = #ij for every j = 1, . . . , i. It is important here that |wi | = i
for i = 1, . . . , m. Then, we can see that given quorum θ ≥ 2, any motif occurs only inside
blocks and consists only of ◦ and aj ’s. Furthermore, there is a one-to-one correspondence
between all θ-frequent itemsets in r and all θ-motifs in s for θ ≥ 2. We see that the lattice(FIθ , ⊆) of all frequent itemsets in r is isomorphic to the lattice (Fθ , ¹) of all motifs ins (see full paper for details). This induces a one-to-one correspondence between all closed
itemsets in r and all maximal motifs in s. Thus, the result immediately follows.
2
Theorem 2. There is an infinite series of input strings s0 , s1 , s2 , . . . , such that for everyi ≥ 0 with quorum θ = 12 N , the number F = |F| of motifs in si is exponential (moreprecisely 2Ω(N ) ) in the input size N , while the number M = |M| of maximal motifs in si
is linear in N , where N = |si |.
Proof: Theorem 1 of Uno et al. [15] says that there is an infinite series of transaction
databases such that the number F of frequent itemsets and the number M of frequent
closed itemsets in a transaction database of size mn are F = 2Ω(n) and M = O(m2 ),respectively. Combining Lemma 3 above and the constructions of Theorem 1 of [15], whereN = Θ(m2 ) for large m and n, we obtain the result.
2

B

Proof of Theorem 8

In this section, we prove Theorem 8 of Section. We start with the following technicallemmas.
Lemma 12. For any string xy ∈ Σ(Σ ∪ {◦})∗ , L(xy) = L(x) ∩ (L(y) + |x|).
Lemma 13. Let x, y be any motifs. If L(x) = L(y) then L(xξ) = L(yξ) for any substitution ξ = hk ← ci compatible to both x and y.
For any string x ∈ (Σ ∪ {◦})∗ , x[0..k − 1] denotes the prefix of x with length k if
|x| ≥ k. If |x| < k, then x[0..k − 1] denotes the string of length k obtained from x bypadding trailing ◦’s, i.e., x[0..k − 1] = bxc[0..k − 1].
Lemma 14. Let y be any maximal motif such that y 6= ⊥ and ` be the core index of y.
For the parent x = P(y) of y, x[0..` − 1] = y[0..` − 1] holds.
Proof: Let x = Clo(y[0..` − 1]) = P(y). By construction, y[0..` − 1] ¹ x[0..` − 1]. Suppose
to contradict that x[0..` − 1] 6= y[0..` − 1], that is, the closure operation filled some positioni < ` in y[0..` − 1] with a solid letter. Then, we have y[0..` − 1] ≺ x[0..` − 1] (*1). Now,12

let y 0 = x[0..` − 1]y[`..|y| − 1] be a new string obtained from y by replacing the prefix
y[0..` − 1] with x[0..` − 1]. Clearly, y ≺ y 0 . On the other hand, from (2) of Lemma 7,
we have L(x[0..` − 1]) = L(y[0..` − 1]) + d for some d since x = Clo(y[0..` − 1]) andL(Clo(y[0..` − 1])) = L(y[0..` − 1]) + d for some d. By Lemma 12, we can show thatfor any strings x1 , x2 , y1 , y2 ∈ Σ(Σ ∪ {◦})∗ , if L(x1 ) = L(x2 ) and L(y1 ) = L(y2 ) thenL(x1 y1 ) = L(x2 y2 ). Thus, if L(x[0..` − 1]) = L(y[0..` − 1]) then we have L(y 0 ) = L(y)(*2). It follows from (*1) and (*2) that y is not maximal. This is the contradiction, andthus we conclude that x[0..` − 1] = y[0..` − 1].
2
Lemma 15. Let x be any maximal motif and y = Clo(xhk ← ci) be a ppc-extension of x.
Then, k is the core index of y.
Proof: Let ξ = hk ← ci be the substitution generating y = Clo(xξ). (a) By definitionof ppc-expansion, k − 1 ≥ core i(x) and x[0..k − 1] = y[0..k − 1] hold. Thus, we haveL(x) = L(x[0..k − 1]) = L(y[0..k − 1]). Since x is maximal, any substitution ξ results|L(x)| =6 |L(xξ)| = |L(y)|. Therefore, we have L(y[0..k − 1]) 6= L(y). (b) Next, we showthat L(y[0..k]) = L(y). Firstly, from assumptions, x[k] = ◦, y[k] = c, and x[0..k − 1] =y[0..k − 1] hold. This implies that y[0..k] = xξ[0..k], and thus that L(y[0..k]) = L(xξ[0..k])(*1). Next, if k > core i(x) then we have L(x[0..k]) = L(x). By applying Lemma 13,
it follows that L(y[0..k]) = L(x[0..k]ξ) = L(xξ) (*2). Finally, from (2) of Lemma 7, if
y = Clo(xξ) then L(xξ) = L(Clo(xξ)) + d = L(y) + d for some d (*3). Combining (*1)–(*3), we have L(y[0..k]) = L(y) + d for some d. Since y[0..k] is a prefix of y, we can showthat d = 0 must hold. From (a) and (b), we know that k is the core index of y.
2
Lemma 16. For any maximal motif y such that y 6= ⊥, if x = P (y) then y is a prefixpreserving expansion Clo(xξ) of x for some ξ = hk ← ci ∈ Z × Σ.
Proof: Suppose that x = P(y). Then, x = Clo(y[0..` − 1]) for the core prefix ` = core (y)of y. Let k = ` and c = x[`]. Then, we can show that x[`] = ◦ because x = Clo(y[0..`−1]) ≺Clo(y[0..`]) = y. Thus, the substitution ξ = h` ← ci is compatible to x. Now, we show thaty = Clo(xξ) for ξ = h` ← ci. First, we show L(x) = L(x[0..` − 1]). By (2) of Lemma 7,
x = Clo(y[0..` − 1]) implies Clo(y[0..` − 1]) ¹ x. By taking the prefix of length k, we havey[0..` − 1] ¹ x[0..` − 1]. Since x[0..` − 1] is a prefix of x, we have x[0..` − 1] ¹ x. Therefore,
if y[0..` − 1] ¹ x[0..` − 1] ¹ then we have L(y[0..` − 1]) ⊇ L(x[0..` − 1]) ⊇ L(x) (*1). On
the other hand, x = Clo(y[0..` − 1]) since x is the parent of y. Thus, L(y[0..` − 1]) = L(x).
From this, the inclusion in the above inclusion formula is actually equality, that is, we canconclude that L(x[0..` − 1]) = L(x). By Lemma 13, this implies L(xξ) = L(x[0..` − 1]ξ) =L(xξ[0..`]) (*1). On the other hand, by Lemma 14, we know that y[0..` − 1] = x[0..` − 1].
From this, we can show that xξ[0..`] = x[0..` − 1]y[`] = y[0..` − 1][`] = y[0..`], where if thelength of x[0..` − 1] is shorter than k then we appropriately add to x[0..` − 1] by trailing◦’s. Therefore, we have L(xξ[0..`]) = L(y[0..`]) (*2). Since ` is the core index of y, we
have L(y[0..`]) = L(y) (*3). From (*1)–(*3), we have L(xξ) = L(y). By taking the merge
operation of the both side, we have Clo(xξ) = Clo(y) = y since y is a maximal motif andTheorem 4 holds. This completes the proof.
2
Lemma 17. Let x be any maximal motif. If y = Clo(xhk ← ci) is a prefix-preserving
expansion of x for some hk, ci ∈ Z × Σ, then x = P(y) holds.
Proof: Suppose that y = Clo(xhk ← ci). Then, it follows from Lemma 15 that k is
the core index of y. Thus, we have P(y) = Clo(y[0..k − 1]). On the other hand, we havey[0..k−1] = x[0..k−1] and thus Clo(y[0..k−1]) = Clo(x[0..k−1]) since y is a ppc-extensionof x. Since x is maximal, k − 1 ≥ core i(x), we have Clo(x[0..k − 1]) = x. Combining theabove observations, we have P(y) = x.
2
Lemma 18. For all i = 1, 2, let ξi = hki ← ci i ∈ Z × Σ be substitutions and let yi =Clo(xξi ) be the ppc-extension of x generated by ξi . If hk1 , c1 i 6= hk2 , c2 i then y1 and y2 are
distinct.
13

Proof: Assume that ξ1 6= ξ2 and yi = Clo(xξi ) for every i = 1, 2. Suppose to contradictthat y1 = y2 = y for some maximal motif y. Since y is the ppc-expansion of x with
ξ = hki ← ci i, x[0..ki − 1] = y[0..ki − 1] by definition for every i = 1, 2. Thus, eachx[0..ki − 1] is a prefix of y. There are two cases below for k1 and k2 . (a) Suppose first that
k1 = k2 = k. Then, ξ1 6= ξ2 implies c1 6= c2 . However, this is impossible since c1 = y[k] = c2 .
(b) Suppose next that k1 6= k2 . Assume without loss of generality that k1 < k2 . This isagain impossible since Since ξ1 = hk1 ← c1 i is compatible to x, we know that x[k1 ] = ◦and y[k1 ] = c1 . On the other hand, x[0..k2 − 1] = y[0..k2 − 1] must hold for k2 > k1 since
y = Clo(xξ2 ) is the ppc-extension of x. This contradicts that ◦ = x[k1 ] 6= y[k1 ] = c1 .
Hence, by contradiction, we conclude that y1 6= y2 .
2
Proof of Theorem 8: From Lemma 16, Lemma 17, and Lemma 18, the theorem immediately follows.
ut14