平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム

摘要

Balanced Straight line programs (BSLPs) is one of the most powerful and general compression schemes. An BSLP is a context-free grammar which generates only one string. This paper studies an problem on compressed string described in terms of BSLP. In order to process compressed strings emciently(in polynomial time with respect to the compressed size), decompression is never feasible. We show efficient algorithm that testing square-freeness in O(max(n~2,n log~2 N)) time with O(n~2) space, where n and N are the size of a given compressed string and the corresponding decompressed string, respectively.%平衡直線的プログラム（Balanced Straight line program，BSLP）は単元集合を生成する文脈自由文法とみなすことができ，そこで生成される文字列の長さNは，変数の個数nに対して指数的に長くなりうる．そのため，BSLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには，陽に展開することなく処理を行うことが必要不可欠となる．本研究では，BSLPとして表現された文字列の非反復性判定をO（max（n~2，n log~2 N））時間，O（n~2）領域で解くアルゴリズムを示す．