TCS -TR-A-06-19

TCS Technical Report

A Polynomial Space and Polynomial Delay Algorithm
for Enumerating Maximal Two-Dimensional Patterns
with Wildcards
byHiroki Arimura and Takeaki Uno

Division of Computer Science
Report Series A
July 18, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email: Arimura@ist.hokudai.ac.jp

Phone: +81-011-706-7678
Fax: +81-011-706-7890

A Polynomial Space and Polynomial Delay
Algorithm for Enumerating Maximal
Two-Dimensional Patterns with Wildcards
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 ﬁnding maximal patterns in an twodimensional text for the class of two-dimensional picure patterns with wild cards (don’t cares).
A maximal pattern for two-dimensional text is a generalization of a 1-dimensional sequential
motif in (Parida et al., SODA’00; Pisanti et al., MFCS’03; Pelfrene etal., CPM’03), and it
is such a representative pattern that is not properly contained in any larger pattern withthe same location lists under invariance with respect to parallel motion. Since a text may
contain exponentially many maximal patterns in general, it is natural to consider an outputsensitive algorithms for enumerating all patterns in the class. Then, we present a polynomial
space and polynomial delay algorithm for enumerating all maximal patterns in a text array inexact polynomial time per discovered pattern in the total size of the input text. This result
is achieved by backtracking through depth-ﬁrst search of a tree-shaped search route over all
maximal patterns, similar to (Arimura et al., ISAAC’05). We also discuss the lowerboundresults on the number of maximal patterns and the #P-hardness of conting, and eﬃcient input
polynomial time computation of constant patterns with matrix suﬃx trees.

1

Introduction

By rapid increase of electronic data in various forms, two dimensional pattern matching have received much attention with potential applications in multimedia, digital
libraries, computer vision, geographic information systems and semi-structured dataprocessing. In this paper, we consider a new class of data processing problem for
two-dimensional matrix data, called the two-dimensional pattern discovery problem,
where an input is a n×n text matrix T [1..n, 1..n] over an alphabet Σ, the problem is
to ﬁnd all patterns within a pattern class and satisfying speciﬁed constraints without
repetition.
Maximal pattern discovery problem. We study the maximal pattern discovery
problem for the class of square patterns with wild cards deﬁned as follows. For analphabet Σ = {a, b, . . .} of constant letters and the wild card (or don’t care) ◦ ∈ Σ, a
two-dimensinal square pattern with wild cards is an m × m matrix P [1..m, 1..m] overΣ ∪{◦}, where ◦ matches itself and any constant letters. Then, a pattern P [1..m, 1..m]has the location list L(P ) = {d1 , . . . , dm } ⊆ [1..n] × [1..n] (m ≥ 0) which is the set of
all locations (or occurrences) of P in T . A pattern P with wild cards is maximal ina given text T iﬀ (i) P appears in T at some speciﬁed frequency and (ii) there exists

2
no pattern Q appearing in T that properly contains P and having the same location
list under the invariance with respect to parallel motion. We denote by P and M theclass of patterns and the class of all maximal two-dimensional square patterns overΣ ∪ {◦}.
The maximal pattern discovery problem can be regarded as a two-dimensional
string version of maximal motif discovery problems in bioinformatics, extensively studied for the last years [15, 18, 17], and as a variation of closed itemset mining and closed
semi-structured data mining in database and artiﬁcial intelligence areas [11, 20, 21].
Since there are exponentially many patterns in an n × n text (Theorem 2), it isnatural to consider a pattern discovery problem as an enumeration problem. Ourparticular goal here is to devise a polynomial space and polynomial delay algorithm,
which is one of the eﬃcient kinds of output-polynomial time enumeration algorithms,
for solving the maximal pattern discovery problem for two-dimensional patterns withwild cards.
However, preliminary analyses of the problem shows that (Theorem 3) the set of
maximal patterns can be exponentially succinct than the set of all frequent patterns,
and furthermore that (Theorem 4) the counting version of maximal pattern problem
is #P -hard problem indicating that enumeration is a not trivial problem. These results
indicates that a simple generate-and-test approach based on frequent pattern discovery
does not work for our maximal pattern problem.
Main results of this paper. We present an eﬃcient algorithm MaxMatrix that,given an n×n input text T [1..n, 1..n], enumerates all maximal two-dimensional square
patterns P ∈ M with wild cards without duplicates in O(|Σ|N ) exact time (or thedelay) per maximal pattern using O(M) space, where M = m2 is the size of m × m
pattern P and  = |L(P )| = O(N) is the number of occurrences of P in T (Theorem 7).
Then, we modify this algorithm to remove the dependency of |Σ| resulting anotheralgorithm with O(N) exact time per pattern. Since the class of square patterns withwildcards exactly corresponds to the class of two-dimensional patterns of arbitrary
shape, the above results applies to the latter class of patterns. As a special case,
we observe that the maximal pattern enumeration problem for constant patterns issolvable in input polynomial time using dictionary structures (Theorem 1).
The key of our algorithm is a tree-shaped search route built over the space of
all maximal patterns. To realize this idea, we develop a technique, called the preﬁxpreserving closure extension, by combining the previously proposed notions of tailextension and the closure operations.
Organization of this paper. The rest of this paper is organized as follows. In Section 2, we prepare the basic notions and deﬁnitions. Then in Section 3, we show somelower bounds for the number of maximal two-dimensional patterns. In Section 4, wegive our polynomial space and polynomial delay enumeration algorithm MaxMatrix
for the maximal patterns with wild cards. In Section 5, we discuss future directions.

32Preliminaries

We prepare basic deﬁnitions and notations on two-dimensional pattern matching anddiscovery according to [3, 12, 13]. Then, we deﬁne our problem, the maximal twodimensional pattern discovery problem by generalizeing the 1-dimensional maximal
motif discovery problem [8, 15, 18, 17]

2.1

BasicsWe denote by N = {0, 1, 2, . . .} all natural numbers and by Z = N∪{−x | x ∈ N} be all
integers. For any integers i1 , i2 , j1 j2 ∈ Z, we denote the interval [i1 ..i2 ] = { x ∈ Z | i1 ≤x ≤ i2 } and the rectangular region [i1 ..i2 , j1 ..j2 ] = [i1 ..i2 ] × [j1 ..j2 ]. We sometimes
write [m] and [m, n] to denote [1..m] and [1..m, 1..n], respectively.
Let ∆ be an alphabet of symbols. An n×n matrix over ∆, denoted by A[1..m, 1..n],
is a mapping A : [1..m, 1..n] → ∆, where we denote by dom(A) = [1..m, 1..n] the domain of A and by A[i, j] ∈ ∆ the value of A at point (or location) (i, j) ∈ dom(A).
The subarray of A whose domain is [i1 ..i2 , j1 ..j2 ] ⊆ dom(A) is denoted by B =A[i1 ..i2 , j1 ..j2 ]. For m, n ∈ N, we denote by ∆m×n the class of all m × n matrices
over ∆. In what follows, we consider only square matrices, which are matrices withm = n.
2.2

texts and patterns

Let Σ = {a, b, . . .} be an alphabet of solid characters (or constant letters), and ◦ ∈ Σ
be a distinguished letter, called the wild card (or don’t care). A wild card ◦ matches
any solid character c ∈ Σ and also matches ◦ itself. More formally, we deﬁne a binary
relation over Σ ∪ {◦}, called the subsumption relation, as follows: ◦ ◦, ◦ c, andc c for any c ∈ Σ.
Definition 1 (input text matrix). An input text is a n × n matrix T [1..n, 1..n] ∈Σ m×n of solid letters.
Definition 2 (two-dimensional pattern with wild cards). A two-dimensional
pattern with wild cards is a m × m matrix P [1..m, 1..m] ∈ (Σ ∪ {◦}m×m ), where its
border region border(P ) = [1, 1..m] ∪ [m, 1..m] ∪ [1..m, 1] ∪ [1..m, m] contains at least
one solid letters in Σ.3
As a special case, a two-dimensional constant pattern is deﬁned as a m×m matrix
P [1..m, 1..m] ∈ Σ m×m of solid letters only.
3This constraint is to avoid useless patterns wiht large borders ocuppied only by wild cards ◦.

4Definition 3 (occurrence). We say that a square pattern P [1..m, 1..m] ∈ (Σ ∪{◦})m×m with wild cards occurs in another pattern Q[1..n, 1..n] ∈ (Σ ∪ {◦})n×n at
position (x, y) ∈ dom(Q) if P [i, j] Q[x + i − 1, y + j − 1] holds for every position(i, j) ∈ [1..m, 1..m] in P . In this case, we write P
Q. We deﬁne ε occurs in Q at
any position (i, j).
The binary relation is called the subsumption for patterns. For constant patterns,
reduces to the submatrix relation. If P
Q, then, we say that either P subsumes
Q, P is contained by Q, P is more general than Q, or Q is more speciﬁc to P . If
P Q but Q  P , then we deﬁne P ≺ Q and say that either P is properly containedby Q and so on. We can see that if P Q and Q P , then P = Q. Furthermore,is a partial order over P. The converse of Lemma 1 below does not hold in general.
Lemma 1. For patterns with wild cards P, Q in an text T , if P
L(Q).

Q then L(P ) ⊇Definition 4 (two-dimensional pattern of arbitrary shape). A two-dimensional
pattern of arbitrary shape (an arbitrary pattern) is a mapping A : dom(A) → Σ witha ﬁnite domain dom(A) ⊆ Z2 .
In the above deﬁnition, the domain dom(A) can be a non-rectangular region of
Z . We regard (0, 0) as the origin of a pattern A of arbitrary shape. A pattern with
arbitrary shape P occurs in an input text Q at location (x, y) if P [i, j] = Q[x + i −1, y + j − 1] for every (i, j) ∈ dom(P ). It is well known that patterns with wildcards
can be simulated by two-dimensional pattern of arbitrary shape deﬁned below [3](detailed is omitted).
2

Definition 5 (location list). For an input text T [1..n, 1..n] of size n ≥ 0, the location list of pattern P [1..m, 1..m] is the set L(x) ⊆ [1..n, 1..n] of all the positions
p = (x, y) in T at which P occurs.
The frequency of P in T is |L(x)|. A a quorum (or a minimum frequency threshold )is any positive number 1 ≤ θ ≤ n2 . We say that pattern x is a θ-frequent in T [1..n, 1..n]
if |L(x)| ≥ θ holds.
2.3

Maximal Pattern Discovery Problem

Now, we deﬁne the class of maximal two-dimensional patterns by generalizing theclass of 1-dimensional maximal motifs in [15, 18, 17] as follows. For any (xi , yi) ∈ Z2 ,we deﬁne (x1 , y1 ) + (x2 , y2 ) = (x1 + x2 , y1 + y2 ). A displacement is any two-dimensional
vector d = (x, y) ∈ Z2 meaning the parallel motion by d. The shift of a location list
L ⊆ Z2 by displacement d ∈ Z2 is the set L + d = { p + d | p ∈ L }. We write L − x
to represent the set L + y with y = −x. We regard two matrices P and Q as being
equivalent if L(y) = L(x) + d for some d.

5Definition 6 (maximal two-dimensional patterns). A pattern with wild cards
P [1..m, 1..m] is maximal in text T [1..n, 1..n] if for any pattern with wild cards Q[1..m , 1..m ]that properly contains P , i.e., P ≺ Q, there is no displacement d ∈ Z2 such that
L(y) = L(x) + d.
In other words, a pattern P is maximal in T iﬀ there exists no pattern in T thatproperly contains P and is equivalent to P under the invariance with respect to parallel
motion. Without loss of generality, we only consider maximal P with |L(P )| ≥ 2.
We denote by F and M the sets of all frequent patterns and all maximal patterns,
respectively. Clearly, M ⊆ F ⊆ P for any T and any θ. Now, we state our problem
as follows.
Definition 7 (maximal pattern enumeration problem). Let C be a class of
two-dimensional patterns. The maximal pattern enumeration problem for C is, given
an input text T [1..n, 1..n] of size n ≥ 0, to enumerate all maximal two-dimensional
patterns P in T within the class C without repetition.
Since the number of maximal patterns can be exponential in the input size n as
we will see later, the discovery problem naturally becomes an enumeration problem.
2.4

Enumeration algorithms

We introduce terminology for enumeration algorithms according to [14, 19]. Throughout this paper, we adopt the standard RAM model [1] as a model of computation. An
enumeration algorithm for an enumeration problem Π is an algorithm A that receives
an input and prints all solutions without repetition.
Let N, M be the input and the output sizes on an input, and TA be the total
running time of A for computing all solutions. Among eﬃcient enumeration algorithms, the weakest is an output-polynomial algorithm (P-OUTPUT) A, where TA isbounded by a polynomial q(N, M). A is of polynomial enumeration time (P-ENUM)
if the amortized time for each solution x ∈ S is bounded by a polynomial p(N ) in
N, i.e., TA = O(M · p(N )). The strongest is a polynomial delay (P-DELAY) algorithm (or a exact polynomial time enumeration algorithm) A, where the delay, whichis the maximum computation time between two consecutive outputs, is bounded bya polynomial p(N ) in the input size N. A is of polynomial space (P-SPACE) if the
maximum size of its working space is bounded by a polynomial p(N ).
Our goal is to devise an polynomial space polynomial delay enumeration algorithm
for solving the maximal pattern problem for the class of two-dimensional square patterns with wild cards.

3

Lower bound results

We show the following (an upper bound and) lower bound results of the number ofmaximal two-dimensional square patterns with wild cards.

6
The maximal pattern enumeration problem seems rather easy for the special casefor the class of constant two-dimensinal patterns, where the number of maximal patterns in T is clearly bounded above by O(n3) (O(n2 ) patterns for each size m = O(n)).
Acturally, the next theorem, which can be easily derived by combining the previous
results on suﬃx trees for matrices [2, 13], says that the maximal pattern enumeration
problem is solvable in input polynomial time for the class.
Theorem 1 (constant square patterns are easy to enumerate). There exists
an algorithm for enumerating all of n3 maximal patterns in O(n4) = O(N 2 ) total time
for the class of constant two-dimensinal patterns, where N = n2 is the total input size.
Proof: See Appendix A.
On the other hand, we have the following result for maximal patterns with wildcards.
Theorem 2 (exponential lowerbound of maximal patterns). There is an inﬁnite series of input texts T0 , T1 , T2 , . . . , such that for every k = 0, 1, 2, . . ., the number|M| of maximal two-dimensinal patterns with wild cards in Ti is bounded below by
2Ω(n) , where the size of Ti is n × n.
Proof: See Appendix B.
As a technical lemma, we construct below a transformation from an well-studied
problem of closed itemsets enumeration problem to our maximal two-dimensinal pattern enumeration problem.4
Lemma 2 (transformation from closed itemsets to maximal patterns). For
every transaction database R = {t1 , . . . , tm } consisting of m transactions over n itemsof total size N = mn, there exists an ñ× ñ input matrix T with ñ2 = O(N + m2 ) suchthat the number Q of closed itemsets in r is given by Q = M + m − 1, where M is thenumber of maximal patterns with wild cards in T .
Proof: See Appendix C.
Theorem 3 (succinctness of maximal patterns). There is an inﬁnite series of
input strings T0 , T1 , T2 , . . . , such that for every i ≥ 0 with quorum θ = 12 n, the number
F = |F | of all frequent patterns in Ti is exponential (more precisely 2Ω(n) ) in the
input size n, while the number M = |M| of maximal patterns in Ti is polynomial inn, where n = |Ti |.
Proof: The theorem is immediate from Lemma 2 above and the succinctness result
for closed itemsets in [20], where the frequency constraint is not essential.
4

The maximal pattern discover problem in this paper correponds to the closed itemset enumeration fortransaction databases [20] and to the maximal motif disocvery in sequences [16], but not to the maximal
frequent itemset problem.

7

...

n

(a)

(b)

(c) IN1, NE2, NE3, NE4
IN1(i, j)

NE4
m

...

...

j

2

3
2
1

1

10

1

1 2 3 ... i ...

11

12 13

o o B C
7 14
5
6A B B o8 15
2
3
A B B D
9 16
1
4
A o o o
2

... m

n

Fig. 1. (a) The coordinate system, (b) two types of shapes, and (c) the partition genereated by a series ofshapes IN1 + N E2 + N E3 + N E4 .

Theorem 4 (hardness of counting maximal patterns). The maximal pattern
enumeration problem for patterns with wild cards is #P-hard.
Proof: By reduction from the maximal bipartite clique problem, Yan [21] showed thatthe closed pattern enumeration problem for itemsets is #P-hard. Hence, the result
immediately follows from Lemma 2.
From Theorem 3, we know that a popular generate-and-test algorithm based on
frequent pattern discovery does not work in output-polynomial time (See also for
Subsection 4.1). From Theorem 4, we also see that the maximal pattern enumeration
problem is not an easy enumeration problem. This justiﬁes our approach to considering
output-sensitive enumeration algorithms.

4

Polynomial Space Polynomial Delay Algorithm for
Maximal Two-Dimensional Pattern Discovery

4.1

Tail extension

The ﬁrst step towards an eﬃcient algorithm for maximal pattern enumeration is how
to enumerate all two-dimensional maximal patterns without repetition. An obvious
way is to store all the patterns discovered so far on main memory and then to makeexplicit duplicaition check against the stored patterns. However, this appoach requires|M| = 2Ω(n) memory, propotional to the output size, in the worst case.
We introduce a systematic way of partitioning matrices according to Amir andFarach [2] and Giancharlo and Grossi [13]. Let A[1..m, 1..m] ∈ ∆m×m be an m × m
matrix. We assume the coordinate system of Fig. 1 (a) for both texts and patterns,
which is later extended for Z2 as seen in Fig. 2. Let us denote by A + B the union of
two matrices such that dom(A) ∩ dom(B) = ∅ as deﬁned in the standard way. In what
follows, we assume that the locations (i, j) of the plane Z2 are indexed as in Fig. 2.
We partition A[1..m, 1..m] into a series of shapes A = IN1 +NE2 +NE3 +. . .+NEm ,where IN1 is the 1 × 1 square matrix A[1, 1], and NEi is the L-shaped subarray8
NEi (A) = A[1..i, i] + A[i, 1..i − 1] for every 2 ≤ i ≤ m (Fig. 1 (b)). This series ofshapes gives the unique partition of A (Fig. 1 (c)).
Furthermore, we order the positions in the matrix A in the order of A = IN1 +NE2 + NE3 + . . . + NEm , from inside to outside. Then, inside each L-shape NEi (A),we order all of its 2i − 1 positions ﬁrst from left to right then top to bottom as[1, i] < [2, i] < · · · < [i − 1, i] < [i, i] < [i, i − 1] < · · · < [i, 1]. This gives a total order,
denoted by <ord , over m2 positions in the square [1..m, 1..m], where the least positionis the left bottom corner [1, 1, ] and the greatest is the right top corner [m, m] as inFig. 1 (c).
The tail of m × m matrix A ∈ (Σ ∪ {◦})m×m with wild cards is the largest position tail(A) in the order <ord that is labeled by a constant letter, i.e., tail(A) =max<ord { [i, j] ∈ [1..m, 1..m] | A[i, j] ∈ Σ }. For example, the tail of the array inFig. 1 is the cell with order number 15 at position [4, 2] with letter D. We denote by
P [ (i, j) ← c ] the matrix obtained from P by substituting letter c ∈ Σ ∪ {◦} at location(i, j) ∈ dom(P ).
Definition 8 (tail extension of a matrix). A m × m matrix Q is a tail extensionof a m × m matrix P (m ≤ m) if Q = P [(i, j) ← c] for some solid character c ∈ Σand some position (i, j) ∈ N2 such that (i, j) >ord tail(A), where m = max{i, j}.
We consider the directed graph Ttail = (P, E), called an enumeration graph, where
the node set P is the set of all patterns occuring in T at least once and E is the edge
set such that (P, Q) ∈ E iﬀ Q is a tail extension of P . Then, we can see that Ttail isa spanning tree for all members of Pm since P = Q[ tail(Q) ← ◦ ] obtains P as theunique parent pattern of Q and |P |Σ < |Q|Σ . Thus, we have the next lemma.
Lemma 3. There is an algorithm that enumerates all matrix patterns with wild cards,
up to maximum size m ≥ 0, without repetition in O(1) time per patterns based on thedepth-ﬁrst search over Ttail .
Proof: By traversing this tree starting from the empty matrix ⊥ as the unique root
using backtracking, the claimed time complexity is obtained.
From the above lemma, the following approach for maximal pattern enumeration ispossible: it is ﬁrst to enuemerate all patterns with frequency at least two, and then test
if each candidate pattern is maximal and if it is not duplicated. However, From thesuccinctness result in Theorem 3, this method takes exponential time in the numberof maximal patterns in the worst case. Thus, the tail extension alone does not help
to give even output polynomial time algorithms.
4.2

Merge and Closure

The second problem to solve is how to eﬃcently check maximality of patterns without storing all discovered patterns so far. First, we extend the merge and the closure

9
operations, which are originally introduced in [5, 9, 17, 18], then we give a characterization of maximal two-dimensional patterns with wildcards. We start with technicaldeﬁnitions.
Definition 9. We deﬁne a pseudo two-dimensional matrix to be a mapping P : Z2 →Σ∪{◦} with inﬁnite domain dom(P ) = Z2 , where P [i, j] ∈ Σ is deﬁned only for ﬁnitely
many points (i, j) ∈ dom(P ) and other points are ﬁlled with wild cards ◦.
We deﬁne the shift of P by a displacement d = (x, y) ∈ Z2 , denoted by (S + d),
as the pseudo matrix such that (S + d)[i, j] = S[i − x, j − y] for every (i, j) ∈ Z2 . By
this transformation, the origin o = (0, 0) of P moves to the point d = (x, y).
For each two-dimensional pattern P [1..m, 1..m] with wild cards, its inﬁnite version is the two-dimensional pseudo matrix P  : Z2 → Σ ∪ {◦}, where the value
S[i, j] = S[i, j] if (i, j) ∈ dom(S) and S[i, j] = ◦ otherwise. Conversely, for eachtwo-dimensional pseudo matrix S : Z2 → Σ ∪ {◦}, we deﬁne the trimmed version of S
by the m×m matrix S = S[x..x + m − 1, y..y + m − 1] − (x, y) with wildcards, where
xmin and ymin (xmin and ymin , resp.) are the smallest (largest, resp.) x-coordinates andy-coordinates for the locations of solid letters in S.
Next, we deﬁne the merge operator ⊕ for two-dimensional pseudo matrices asfollows. For letters a, b ∈ Σ, we deﬁne a ⊕ a = a and a ⊕ ◦ = ◦ ⊕ a = a ⊕ b = ◦ ifa = b. This operator ⊕ is associative and commutative. The merge of two-dimensional
pseudo matrices X, Y : Z2 → ∆ is the two-dim pseudo matrix X ⊕Y : Z2 → ∆ deﬁned
by X ⊕ Y [i, j] = X[i, j] ⊕ Y [i, j] for every point (i, j) ∈ Z2 .
Definition 10. Let T be an input text. The merge of a location list L = {d1 , . . . , d|L| } ⊆dom(T ) is the pseudo string
L : Z2 → ∆ deﬁned by
L = (T  − d1 ) ⊕ · · · ⊕ (T  − d|L| ).

Then, its trimmed version is a two-dimensional pattern given by P =  L ∈ P.
Lemma 4. Let L, L be any location lists and d ∈ Z2 be any displacement.
 
1. If L ⊇ L + d then
L
L.


2.
L = (L + d) for any integer d.
Proof: 1: For sets A, A ⊆ ∆ of letters, if A ⊇ A then ⊕A ⊕A . Let p = (i, j) be
any position and put A = { T [p + d] | d ∈ L } and A = { T [p + d] | d ∈ L }. Since 
L[p] = ⊕A ⊕A =L [p]. This proves the property. 2:
A ⊆ A , we can see that
Immediately from the above.

Lemma 5. Let L ⊆ [1..n, 1..n] be any location list in T . Then, P =  L is a
maximal pattern.

10
The following deﬁnition is a generalization of the closure operator for itemsets [20]and sequence motifs [17, 18].
Definition 11 (closure operation ). Given a pattern x and an input string s, themaximal pattern Clo(x) =  L(x) is called the closure of x on s.
Lemma 6. The closure Clo(P ) of a pattern P is unique and computable in O(n2 ) =O(N ) time from P and L(P ), where N = n2 and  = |L(P )| ≤ n.
Lemma 7 (properties of closure). Let P, Q be any patterns occurring in T and
P, Q be any location lists.
1. P Clo(P ).
2. Clo(P ) = Clo(Clo(P )).
3. L(P ) = L(Clo(P )).
4. If P Q then Clo(P ) Clo(Q).
5. Clo(P ) is the unique maximal member in { Q | P and Q are equivalent on T }, theequivalence class of patterns with the same location lists.
The following theorem is a two-dimensional version of a therem in [17].
Theorem 5 (characterization of maximal patterns). Let θ a quorum and P [1..m, 1..m]be a pattern in a text T [1..n, 1..n]. Then, the following (i)–(iii) are equivalent:(i) P is a maximal pattern.
(ii) P =  L for some L ⊆ [1..n, 1..n].
(iii) P = Clo(P ).
Let ⊥ be the (smallest) maximal pattern equivalent to the empty ⊥ pattern, called
the root maximal pattern. Recall that in Lemma 1, the subsumption and the inclusion ⊇ between location lists do not coincide for two-dimensional patterns with wildcards. The following lemma says that they coincide for maximal patterns.
Lemma 8. For maximal patterns P, Q ∈ M on an input text T , P
L(Q).

Q iﬀ L(P ) ⊇A possible use of the closure operation is to deﬁne the closure extension Q of asquare matrix P [1..m, 1..m] by Q = Clo(P [(i, j) ← c]). Then, repeating the closure
extension iteratively patterns starting from the root maximal pattern ⊥, this method
acturally generates all maximal patterns. Since the enumeration graph for the patterns
based on the closure extension is a DAG but not a tree unlike Lemma 3, we need
explicit duplicate check storing all discovered patterns using the memory proportional
to the output size M. Thus, this approach, may result an output polynomial timealgorithm, but cannot be a polynomial delay polynomial space algorithm. Thus, theclosure extension alone still does not help to solve our problem.

11
4.3

Prefix Preserving Extension for Two-dimensional Patterns

Now, we give a new extension method that grows a given parent maximal pattern togenerate more speciﬁc children maximal patterns by combining the tail extension andthe closure operator above. In this subsection, we adopt the framework of the reverse
search of Avis and Fukuda [10] in order to build an enuemration algorithm based on
backtracking over a tree-shaped search route.
An enumeration tree for M. First, we construct an enumeration tree Tppc =(M, Eppc ) for all maximal two-dimensional patterns of M appearing in an input text
T . To construct the tree Tppc , we associate with each non-bottom pattern Q ∈ M\{⊥}the unique parent pattern P = P a(Q) ∈ M of smaller size as follows.
Let Q[1..m, 1..m] be an m × m pattern with wild cards. Recall that the indexes of
Q is totally ordered by <ord according to the shape sequence IN1 , SE2 , SE3 , . . . , SEm
as in Fig. 1 (c). Given any position (i, j), the preﬁx with tail (x, y) is the subset pref ix(i, j) = { (i, j) ∈ [1..m, 1..m] | (0, 0) ≤ ord (i, j) ≤ ord (x, y) }, where m =max{x, y}. Then, we denote by Q ∩ pref ix(x, y) the submatrix of Q with the domaindom(Q) ∩ pref ix(x, y).
Definition 12 (core position). The core position of Q, denoted by core p(Q), is
the smallest position that the corresponding preﬁx preserves the location list of Q,
that is,core p(Q) = min{ (x, y) ∈ dom(Q) | L(Q ∩ pref ix(x, y)) = L(Q) }.
Then, we call the core preﬁx of Q the pattern R = pref ix(x, y) ∩ Q.
Definition 13 (parent in ppc-extension). Let Q be an m × m pattern with wildcards and (x, y) = core p(Q) is the core position of Q. Then, the parent of Q is thepattern P a(Q) given by
P a(Q) = Clo(CP [tail(CP ) ← ◦]),
where CP = pref ix(x, y) ∩ Q is the core preﬁx of Q and CP [tail(CP ) ← ◦] is thepattern obtained from CP by removing its tail by substitution a wild card for the tailposition.
On the other words, P a(Q) is the two-dimensional pattern obtained from the corepreﬁx of Q by removing the solid letter at the tail position. Now, we have the parentchild relation for Tppc = (M, Eppc). M is the set of all maximal patterns appearing in
an input text T , and E is the edge set such that (P, Q) ∈ E iﬀ P is a parent of Q in
ppc-extension (Deﬁnition 13).
Lemma 9. The enumeration graph Tppc for M is a spanning tree for M.

12∞

The substitution point (x, y)...

m
The prefix of P
= prefix(x,y)(in white)
−∞

...

2
1
0
...

The 3rd quadrant:prohibited region

The 1st quadrant:
mixed region

pattern P...

The 2nd quadrant:prohibited region

−2 −1
−2

o C
o o
A B
A B
A o

o o B
B C o
B o o
B D o
o o o

0 1 2 ... m ...

The safe region of R
= P[(x,y) ← c)]= [1..∞,1..∞] - prefix(x,y)(in gray)
The core index core_p(P)∞The 4th quadrant:prohibited region

Fig. 2. The safe region and the prohibited region in the preﬁx-preserving closure extension (ppc-extension).

Proof: Since the core preﬁx and the closure are uniquely determined from their inputs,
the parent P a(Q) is well-deﬁned and unique. Thus, each node Q other than thebottom ⊥ has the unique parent. On the other hand, since the core preﬁx is theshortest preﬁx preserving the location list L(Q), P a(Q) must have a properly larger
location list, i.e., L(P a(Q)) ⊃ L(Q). From Lemma 8, we have that P a(Q) ≺ Q, andthat |P a(Q)|Σ < |Q|Σ . Therefore, we know that Tppc has no inﬁnitely descending
sequences w.r.t. . Combining the above arguments, we proved the lemma.
A depth-first search algorithm for M. Now, we have an enumeration tree Tppc
for maximal two-dimensional patterns in M. However, it is a bit complicated toperform a depth-ﬁrst search on Tppc because the edges of the tree are directed froma child to the parent in the reverse direction. Thus, the remaining task is to give aneﬃcient procedure to, given a parent maximal pattern P , enumerate all of its children
Q uniquely. This is achieved by the following PPC-extension, which is obtained by
combining the tail extension and the closure operation.
Let P be any maximal pattern. If we substitute any solid letter c ∈ Σ for any
location (x, y) ∈ dom(x, y) of a wild card, i.e., P [x, y] = ◦, then from the maximalityof P , we see that the resulting pattern R = P [ (x, y) ← c ] has a properly smaller
location list L(R) ⊂ L(P ) than the original one. Then, we compute the merge Q =⊕L(R) of L(R). By Theorem 5, Q is ensured to be a maximal pattern in T , andfrom Lemma 8, Q is properly more general than P , i.e., P ≺ Q. However, the wrong
choice of the substituted position (x, y) causes the duplicated generation of the same
pattern through exponentially many distinct paths from the root. Thus, we needcareful application of the substitution and the merge.
By deﬁnition, Q = ⊕L(R) above is a pseudo pattern Q : Z2 → (Σ ∪ {◦})
whose domain dom(Q) may contain some positions with negative coordinates. Let[1..∞, 1..∞] = N2 be the ﬁrst quadrant of the plane Z2 as an open region. Let (x, y) ∈dom(P ) be the index of P to be subsituted. Then, the safe region for ppc-extension
is deﬁned by the set [1..∞, 1..∞] − pref ix(x, y) = { (i, j) ∈ N2 | (i, j) >ord (x, y) },where the total order <ord is naturally extended for [1..∞, 1..∞].

13
Definition 14 (ppc-extension). Let P ∈ M be any maximal two-dimensional pattern in T . Then, a two-domensional pattern Q is said to be a preﬁx-preserving closure
extension (ppc-extension, for short) of P if the following (i)–(iii) are satisﬁed:(i) Closure extension: Q is obtained by substitution of a solid character and application of the closure operation, i.e, Q = Clo(P [ (x, y) ← c ]) = ⊕L(P [ (x, y) ← c ])
for some c ∈ Σ and some position (x, y) ∈ dom(P ) satisfying P [x, y] = ◦.
(ii) Tail extension: The position (x, y), called the substitution point, properly follows
the core position of P , i.e., (x, y) >ord core p(P ).
(iii) Preﬁx checking: The extension adds new solid letters to P only to its safe region,i.e., dom(⊕L(P [ (x, y) ← c ])) ⊆ dom(P ) ∪ { (i, j) ∈ N2 | (i, j) >ord (x, y) }.5
Lemma 10. Let T be an n × n input text. Then, all ppc-extensions of a maximalm × m pattern P can be computed in O(|Σ|N 2 ), where N = n2 .
Lemma 11. Let P be any maximal pattern and Q = ⊕L(P [ (x, y) ← c ]) be a ppcextension of P . Then, (x, y) is the core position of Q.
Theorem 6 (correctness of ppc-extension). For any maximal two-dimensional
pattern P, Q with wild cards such that Q = ⊥. Then, (1) P = P a(Q) if and only if(2) Q = ⊕L(P [ (x, y) ← c ]) is a ppc-expansion of P for some solid letter c ∈ Σ andfor some location (x, y) ∈ dom(P ) of wild card ◦. Furthermore, there exists exactly
one pair of (x, y) and c satisfying condition (2) for each Q.
Proof: A sketch of proof. (only-if part) If P = P a(Q) then P = Clo(CP [tail(CP ) ←◦]) for the core preﬁx CP of P . If c = CP [tail(CP )] then we can prove that Q =P [tail(CP ) ← c] is a ppc-extension of P . (if part) If Q is a ppc-extension of P
then Q = ⊕L(P [ (x, y) ← c ]) for some solid letter c ∈ Σ and position (x, y) >org
core p(P ). Then, we can see that (x, y) = core p(Q). Furthermore, we can show that
P a(Q) = Clo(Q ∩ pref ix(x, y)[(x, y) ← ◦]) = P . This completes the proof.
Based on Theorem 6, we present in Fig. 3 our algorithm MaxMatrix that enumerates all maximal two-dimensional patterns in a given input text by the depth-ﬁrst
search over the enumeration tree Tppc for M applying the ppc-extension to each maximal patterns. From the aruguments so far, we have the main result of this paper. To
diminish the factor on the delay proportional to the depth of the enumeration tree,
we use the technique of Uno [19].
Theorem 7 (main theorem). Given an n × n input text T , the algorithm MaxMatrix in Fig. 3 enumerates all maximal two-dimensional square patterns P withwild cards within M in O(|Σ|N ) amortized time per maximal pattern with O(M)
space and O(|Σ|N ) delay, where N = n2 is the total input size, M = m2 is the sizeof m × m pattern P being enumerated, and  = |L(P )| = O(N) is the number ofoccurrences of P .
5

Note that we did not apply the trimming operation · in order to avoid shifting the origin of ⊕L(R) until
this cheking step is done.

14
Algorithm MaxMatrix(Σ: alphabet of constants, T [1..n, 1..n]: input text matrix)
0 ⊥ = Clo(⊥);//the root pattern.
1 call Expand(⊥, (0, 0), T );//(0, 0) <ord (i, j) for any (i, j).
Procedure Expand(P : motif, (px , py ): core position, T : input matrix)
1 //assumption: core p(P ) = (px , py ) is ensured.
2 output P ;3 foreach (x, y) ∈ [1..n, 1..n] s.t. (x, y) >ord (px , py ) do
4
foreach c ∈ Σ do begin
5
R = ⊕L(P [ (x, y) ← c ]);//ppt-extension.
6
Saf eRegion(x, y) = { (i, j) ∈ [1..n, 1..n] | (i, j) >ord (x, y) };7
if (dom(⊕L(R))\dom(P )) ⊆ Saf eRegion(x, y) then8
Q = R;
9call Expand(Q, (x, y), T );10
end forFig. 3. A polynomial space polynomial delay enumeration algorithm for maximal two-dimensional patterns
M in an input text matrix.

Corollary 1. The maxmal pattern enumeration problem is enumerable in polynomial
space and polynomial delay in the input size for the following classes:• the class of two-dimensional square patterns with wild cards.
• the class of two-dimensional patterns of arbitrary shape.
Proof: The second result follows from the ﬁrst result since patterns of the second classcan be simulated by the patterns of the ﬁrst class.

Procedure Expand(P : motif, (px , py ): core position, T : input matrix)
output P ;Initialize the hash L ⊆ [1..n, 1..n]× Σ;
foreach location (i, j) ∈ L(P ) do
foreach (x, y) ∈ [1..n, 1..n] s.t. (x, y) >ord (px , py ) doL(x, y, c) = L(x, y, c) ∪ {(i + x, j + y)}, where c = T [i + x, j + y];foreach (x, y, c) ∈ L do
L(P ) = L(x, y, c);Compute the ppc-extension Q of P with subsutitution [ (x, y) ← c ] as line 5 to line 8 of the original;
Expand(Q, (x, y), T );end forFig. 4. A modiﬁed version of the recursive procedure Extend

Removing the dependency on the alphabet size. We show that the dependencyof the delay time on |Σ| of the algorithm MaxMatrix in Theorem 7 is remove by a
modiﬁcation based on the occurrence-deliver technique in Uno et al. [20].
Corollary 2 (modified algorithm). The algorithm MaxMatrixModified of Fig. 4
enumerates all maximal two-dimensional square patterns P with wild cards within M
in O(N) amortized time per maximal pattern with O(M) space and O(N) delay,
where the parameters N, M, and  are the same as Theorem 7.

155Conclusion

In this paper, we study the problem of enumerating all maximal square patterns withwild cards in a given n×n input matrix of symbols without duplicates. We presented
a polynomial space and polynomial delay algorithm, MaxMatrix, for the problem
by adopting the framework of reverse search [10].
We considered a version of pattern discovery problem where only parallel motion
is allowed as geometrical transformation. For two-dimensional string matching, there
are a number of variations such matching with rotation, enlargement, transpose, andwith mismatch and approximate match [3, 12]. Thus, it is a future research to consider
two-dimensional pattern discovery problems with the above extensions. In this paper,
we used a class of matrix suﬃx trees [13] for maximal constant pattern problem. The
speedup of the presented algorithm incorporating matrix suﬃx trees will be anotherresearch issue.
Boros et al. [11], Apostolico, Comin, and Parida [6], Uno and Arimura [8, 9, 20]
studied eﬃcient solutions of maximal pattern enumeration problems for some classesof structured objects other than two-dimensinal matrices. It would be an interesting problem to develop a uniform algorithmic scheme to construct polynomial space
polynomial delay enumeration algorithms for a class of such structured objects.
We are presently implementing the algorithm MaxMatrix developed in this paper. We plan to make experimental study about the practical performance and theutility for applications, and will include some results of preliminary experiments inthe complete paper.

Acknowledgments
The authors would like to thank Matteo Comin for providing the materials on their
output-polynomial time algorithm for maximal motif discovery for sequences. The ﬁrst
author is grateful to Shin-ichi Shimozono for discussion on geometric discovery, andto Tatsuya Asai, Takuya Kida, Seishi Okamoto, Masayuki Takeda, Ayumi Shinohara,
Shin-ichi Minato, and Thomas Zeugmann for discussions on pattern matching andpattern discovery in non-standard texts and semi-structured data mining.

References
1. A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, AddisonWesley, 1974.
2. A. Amir, M. Farach, Two-dimensional dictionary matching, Information Processing Letters, 44, 233–239,
1992.
3. A. Amir, M. Farach, Two Dimensional Matching, In A. Apostolico, Z. Galil (eds), Pattern Matching
Algorithms, Chapter 9, Oxford University Press, 1997.
4. A. Apostolico, Z. Galil, Pattern Matching Algorithms, Oxford University Press, 1997.
5. A. Apostolico and L. Parida, Compression and the wheel of fortune, In Proc. the 2003 Data Compression
Conference (DCC’03), IEEE, 2003.

16
6. A. Apostolico, M. Comin, L. Parida, Mining, Compressing and Classifying with Extensible Motifs
Manuscript, 2006. (to appear in BMC Algorithms for Molecular Biology, 2006.)
7. A. Apostolico, M. Comin, L. Parida, Conservative extraction of over-represented extensible motifs,
Bioinformatics, 21, Suppl. 1, 9-18, 2005.
8. H. Arimura, T. Uno, A polynomial space polynomial delay algorithm for enumeration of maximal motifs
in a sequence, In Proc. the 16th Annual International Symposium on Algorithms and Computation(ISAAC’05), LNCS 3827, Springer, 2005.
9. H. Arimura, T. Uno, An output-polynomial time algorithm for mining frequent closed attribute trees,
In Proc. ILP’05, LNAI 3625, 1–19, August 2005.
10. D. Avis, K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, 65(1–3), 21–46,
1996.
11. 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.
12. M. Crochemore and W. Rytter, jewels of Stringology: Text Algorithms, World Scientiﬁc, 2003.
13. R. Giancarlo, R. Grossi, Suﬃx Tree Data Structures for Matrices, In A. Apostolico, Z. Galil (eds),
Pattern Matching Algorithms, Chapter 10, Oxford University Press, 1997.
14. L. A. Goldberg, Polynomial space polynomial delay algorithms for listing families of graphs, In Proc. the25th STOC, ACM, 218–225, 1993.
15. 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 eﬀcient polynomial time algorithm, In Proc. the11th SIAM Symposium on Discrete Algorithms (SODA’00), 297–308, 2000.
16. L. Parida, I. Rigoutsos, D. E. Platt, An Output-Sensitive Flexible Pattern Discovery Algorithm. In
Proc. CPM’01, LNCS 2089, 131–142, 2001.
17. J. Pelfrêne, S. Abdeddaïm, and J. Alexandre, Extending Approximate Patterns, In Proc. CPM’03,
LNCS 2676, 328–347, 2003.
18. 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.
19. T. Uno, Two general methods to reduce delay and change of enumeration algorithms, NII Technical
Report, NII-2003-004E, April 2003.
20. T. Uno, T. Asai, Y. Uchida, H. Arimura, An eﬃcient algorithm for enumerating closed patterns intransaction databases, In Proc. DS’04, LNAI 3245, 16-30, 2004.
21. G. Yang, The complexity of mining maximal frequent itemsets and maximal frequent patterns,
In Proc. the 10th ACM SIGKDD international conference on Knowledge discovery and data mining(KDD’04), 344 - 353, 2004.

17

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

A

Proof of Theorem 1

Theorem 1 (constant square patterns are easy to enumerate): There exists
an algorithm for enumerating all of n3 maximal patterns in O(n2) total time for theclass of constant two-dimensinal patterns is solvable in input polynomial time.
Proof: Let N = n2 . For each direction δ ∈ {N E, NW, SE, SW }, we construct Lsuﬃx tree T δ for an input text T [1..n, 1..n] in O(N log n) time [2, 13]. For constantsquare patterns, we can show that if P [m, m] is maximal in T with at least two
locations in T then P has the corresponding explicit node in T δ for each δ. We
enumerate all of such candidate patterns P by traversing O(N) explicit nodes of
one tree, say, T N E , and for each P , test if P has an explicit locus in T δ for eachδ ∈ {N W, SE, SW } in O(m2 ) = O(N) per pattern P . Overall, this straightfoward
method takes Ttotal = O(N log n + N 2 ) = O(n4 ) time to solve the maximal patternproblem for constant square patterns.

B

Proof of Theorem 2

Theorem 2 (exponential lowerbound of maximal patterns): There is an
inﬁnite series of input texts T0 , T1 , T2 , . . . , such that for every k = 0, 1, 2, . . ., thenumber |M| of maximal two-dimensinal patterns with wild cards in Ti is bounded
below by 2Ω(n) , where the size of Ti is n × n.
Proof: Let k ≥ 0, n = k 2 and T = Tk be an n × n matrix deﬁned as follows. First,
we partition T into k 2 square submatrices B1 , . . . , Bk2 of size k × k, and for each
Bi , we number the k × k locations in Bi as pi1 , . . . , pik2 . Then, we deﬁne Bi [pi1 ] = $,and for each j > 1, Bi [pij ] = 1 if i = j and Bi [pij ] = 0 otherwise. Next, we deﬁne
the set X consisting of the patterns P : [1..k, 1..k] obtained from arbitrary k × kpatterns over the alphabet {0, ◦} by putting P [1, 1] = $. Then, we can see that
2
L(P ) = { pij | 1 ≤ i ≤ k 2 , P [pj ] = ◦ }. Since all 2k −1 patterns have mutually distinct
location lists in T , there at least the same number of maximal patterns in T .

C

Proof of Lemma 2

Lemma 2 (transformation from closed itemsets to maximal patterns): Let
I = {1, . . . , n} be items. For every transaction database R = {t1 , . . . , tm } consistingof m transactions over n items of total size N = mn, there exists an ñ×ñ input matrix
T with ñ2 = O(N + m2 ) such that the number Q of closed itemsets in r is given by
Q = M + m − 1, where M is the number of maximal patterns with wild cards in T .
Proof: We assume that m ≤ n and all members of R are mutually distinct. Supposethat n = k 2 and m = 2 for some k,  ≥ 0. Let ñ = k + 1/22 . Σ = { 1j , 0ij , #ii | a ∈18I, 1 ≤ j ≤ n, 1 ≤ i, i ≤ ñ }. We deﬁne a text T [ñ × ñ] as follows. First, we number the
positions in [1.., k, 1..k] as p1 , . . . , pk2 . For each ti , we deﬁne the k × k matrix Ai as
Ai [pj ] = 1j if xj ∈ ti and Ai [pj ] = 0j . otherwise. We arrange k 2 matrices Ai ’s in T in k
rows and k columns, where i-th column and (i + 1)-th column of A’s are separated by
a #-column V Di of width i and j-th row and (j + 1)-th row HDj of A’s are separatedmby a #-row of height i. For all (i, j) ∈ B = (V Di )mi=1 ∪ (HDj )j=1 , we assign mutually
distinct value T [(i, j)] = #ij . Then, we can show that for a square pattern P with
|L(P )| ≥ 2, any of its occurrence is entirely contained in some submatrix Ai . We canshow that the number Q2 of closed itemsets appearing at least twice in r equals thenumber M2 of maximal matrix appearing at least twice in T . Since Q = Q2 + m and
M = M2 + 1 and ñ2 = O(k 2 2 + k3 + 1/44), the result follows from Q − m = M − 1.