2009 Computing: The Australasian Theory Symposium

held in Wellington, New Zealand January 20-23 2009.

Guest Editors: Rod Downey, Victoria University of Wellington, NZ

Prabhu Manyem, Shanghai University, PRC.

Article 2010-7

Published by the Department of Computer Science, The University of Chicago.

An Efficient Algorithm
to Test Square-Freeness of Strings
Compressed by Balanced Straight Line Programs

Wataru Matsubara
Graduate School of Information Sciences
Tohoku University, Japan,
Shunsuke Inenaga
Graduate School of Information Science and Electrical Engineering
Kyushu University, Japan
and
Ayumi Shinohara
Graduate School of Information Sciences
Tohoku University, Japan
June 22, 2010

Abstract

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 = u^k implies k = 1 and u = z. A string w is said to be square-free if no substrings of w are squares. However, very little is known for testing square-freeness of a given compressed string. In this paper, we give an O( max(n^2, n log^2 N))-time O(n^2)-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(2^n). Hence no decompress-then-test approaches can be better than our method in the worst case.

The article: PDF (282,992 bytes)
Source materials: ZIP (175,783 bytes)
Self citation in BIBTeX (205 bytes)
Original version (pre-June 2010): PDF (328,293 bytes)

DOI: 10.4086/cjtcs.2010.007