*
*

*
*

- In this paper we study the problem of deciding
whether a given compressed string contains a square.
A string x is called a square if x = zz and z = uk
implies k = 1 and u = z. A string w is said
to be square-free if no substrings of w are squares.
Many efficient algorithms to test if a given string
is square-free, have been developed so far. However,
very little is known for testing square-freeness
of a given compressed string. In this paper, we
give an O(max(n2, n log2 N))-time O(n2)-space solution
to test square-freeness of a given compressed
string, where n and N are the size of a given compressed
string and the corresponding decompressed
string, respectively. Our input strings are compressed
by balanced straight line program (BSLP). We remark
that BSLP has exponential compression, that
is, N = O(2n). Hence no decompress-then-test approaches
can be better than our method in the worst
case.

*Note that some of equations in this abstract may have been omitted or may be displayed incorrectly.*