38 citations · 40 across the 2 of their papers we have counts for
2 papers
cs.DS2013★ 2 cited
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 that represents a s…
cs.DM2008★ 38 cited
New Lower Bounds for the Maximum Number of Runs in a String
Kazuhiko Kusano, Wataru Matsubara, Akira Ishino +2
We show a new lower bound for the maximum number of runs in a string. We prove that for any e > 0, (a -- e)n is an asymptotic lower bound, where a = 56733/60064 = 0.944542. It is s…