Detecting regularities on grammar-compressed strings

Tomohiro I, Wataru Matsubara, Kouji Shimohira +5

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 s…