Date: Fri Feb 8 20:36:30 2008
Authors: Atsuyoshi Nakamura, Tomoya Saito and Mineichi Kudo
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.
©Copyright 2008 Authors