An efficient algorithm to test square-freeness of strings compressed by straight-line programs

We give a simple algorithm that, given a straight-line program of size n for a string S of length N, tests whether S   is square-free in O(n4logN) time and O(n2)O(n2) space. The algorithm also allows us to test square-freeness on an arbitrary composition system of size c for S  , in O(c4log5N)O(c4log5N) time and O(c2log2N)O(c2log2N) space, which is faster than using the algorithm by Ga̧sieniec, Karpinski, Plandowski, and Rytter (1996) [4].

► Simple algorithm for square-freeness testing on compressed texts.
► Asymptotically faster than previous methods.
► Describes conversion from arbitrary composition system to small SLPs.