Jun. Jui. 2017 Aug.
SunMonTueWedThuFriSat
25262728293001
02 030405060708
09 101112131415
1617 1819202122
23 242526 27 2829
30310102030405
Click Seminar

Past Seminars

DateJuly 24, 2017 (Monday)
Time16:00-17:00
SpeakerShiho Sugimoto 
Profile
TitleComputing Abelian string regularities based on RLE 
Abstract
Two strings x and y are said to be Abelian equivalent if x is a permutation of y, or vice versa. If a string z satisfies z = xy with x and y being Abelian equivalent, then z is said to be an Abelian square. If a string w can be factorized into a sequence v1,...,vs of strings such that v1 , . . . , vs−1 are all Abelian equivalent and vs is a substring of a permutation of v1, then w is said to have a regular Abelian period (p,t) where p = |v1| and t = |vs|. If a substring w1[i..i+l−1] of a string w1 and a substring w2[j..j + l − 1] of another string w2 are Abelian equivalent, then the substrings are said to be a common Abelian factor of w1 and w2 and if the length l is the maximum of such then the substrings are said to be a longest common Abelian factor of w1 and w2. We propose efficient algorithms which compute these Abelian regularities using the run length encoding (RLE) of strings. For a given string w of length n whose RLE is of size m, we propose algorithms which compute all Abelian squares occurring in w in O(mn) time, and all regular Abelian periods of w in O(mn) time. For two given strings w1 and w2 of total length n and of total RLE size m, we propose an algorithm which computes all longest common Abelian factors in O(m2n) time.
Site