TCS-TR-A-08-35

Date: Fri Feb 8 20:36:30 2008

Title: Algorithms for Finding a Minimum Repetition Structure of a String or a Tree

Authors: Atsuyoshi Nakamura, Tomoya Saito and Mineichi Kudo

Contact:

First name: Atsuyoshi
Last name: Nakamura
Address: Graduate School of Information Science and Technology Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, 060-0814 Japan
Email: atsu@main.ist.hokudai.ac.jp

Abstract. A repetition representation string, RRS for short, is a representation for a set of disjoint or nested tandem arrays in a string. The length of an RRS depends on a set of tandem arrays it represents. We show an O(n^3) dynamic programming algorithm for finding a shortest RRS representing a given string with length n. The algorithm can be extended to an algorithm of the same time complexity for finding a minimum repetition representation tree, RRT for short, representing a given labeled ordered tree with n nodes. Furthermore, corresponding problems for width-k subclasses of RRSs and RRTs are shown to be solved in time O(k^2n) when functions of deciding the size of a RRS and a RRT satisfy a certain condition.