%0 Journal Article %T Detecting regularities on grammar-compressed strings %A Tomohiro I %A Wataru Matsubara %A Kouji Shimohira %A Shunsuke Inenaga %A Hideo Bannai %A Masayuki Takeda %A Kazuyuki Narisawa %A Ayumi Shinohara %J Computer Science %D 2013 %I arXiv %X We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size $n$ that represents a string $s$ of length $N$, our algorithm compute all runs and squares in $s$ in $O(n^3h)$ time and $O(n^2)$ space, where $h$ is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in $O(n^3h + gnh\log N)$ time and $O(n^2)$ space, where $g$ is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in $O(n^2 h)$ time and $O(nh(n+\log^2 N))$ time, respectively. %U http://arxiv.org/abs/1304.7067v1