TCS-TR-A-06-19

Date: Tue Jul 18 22:56:52 2006

Title: A Polynomial Space and Polynomial Delay Algorithm for Enumerating Maximal Two-Dimensional Patterns with Wildcards

Authors: Hiroki Arimura and Takeaki Uno

Contact:

First name: Hiroki
Last name: Arimura
Address: Division of Computer Science, Graduate School of Information Science and Technology Hokkaido University Kita 14-jo, Nishi 9-chome, 060-0814 Sapporo, JAPAN
Email: arim@ist.hokudai.ac.jp

Abstract. In this paper, we consider the problem of finding maximal patterns in an two-dimensional 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 with the 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 output-sensitive 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 in exact polynomial time per discovered pattern in the total size of the input text. This result is achieved by backtracking through depth-first search of a tree-shaped search route over all maximal patterns, similar to (Arimura et al., ISAAC'05). We also discuss the lowerbound results on the number of maximal patterns and the #P-hardness of conting, and efficient input polynomial time computation of constant patterns with matrix suffix trees.