License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-16804
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1680/
Go to the corresponding Portal

Matsubara, Wataru ; Inenaga, Shunsuke ; Shinohara, Ayumi

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

pdf-format:
Document 1.pdf (345 KB)

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. 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(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.

BibTeX - Entry

@InProceedings{matsubara_et_al:DSP:2008:1680,
  author =	{Wataru Matsubara and Shunsuke Inenaga and Ayumi Shinohara},
  title =	{An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program},
  booktitle =	{Structure-Based Compression of Complex Massive Data },
  year =	{2008},
  editor =	{Stefan B{\"o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  number =	{08261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1680},
  annote =	{Keywords: Square Freeness, Straight Line Program}
}

Keywords: Square Freeness, Straight Line Program
Seminar: 08261 - Structure-Based Compression of Complex Massive Data
Issue Date: 2008
Date of publication: 20.11.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI