TY - GEN

T1 - Computing Abelian covers and Abelian runs

AU - Matsuda, Shohei

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Publisher Copyright:
© Czech Technical University in Prague, Czech Republic.

PY - 2014

Y1 - 2014

N2 - Two strings u and v are said to be Abelian equivalent if u is a permutation of the characters of v. We introduce two new regularities on strings w.r.t. Abelian equivalence, called Abelian covers and Abelian runs, which are generalizations of covers and runs of strings, respectively. We show how to determine in O(n) time whether or not a given string w of length n has an Abelian cover. Also, we show how to compute an O(n2)-size representation of (possibly exponentially many) Abelian covers of w in O(n2) time. Moreover, we present how to compute all Abelian runs in w in O(n2) time, and state that the maximum number of all Abelian runs in a string of length n is Ω(n2).

AB - Two strings u and v are said to be Abelian equivalent if u is a permutation of the characters of v. We introduce two new regularities on strings w.r.t. Abelian equivalence, called Abelian covers and Abelian runs, which are generalizations of covers and runs of strings, respectively. We show how to determine in O(n) time whether or not a given string w of length n has an Abelian cover. Also, we show how to compute an O(n2)-size representation of (possibly exponentially many) Abelian covers of w in O(n2) time. Moreover, we present how to compute all Abelian runs in w in O(n2) time, and state that the maximum number of all Abelian runs in a string of length n is Ω(n2).

UR - http://www.scopus.com/inward/record.url?scp=84978384070&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978384070&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84978384070

T3 - Proceedings of the Prague Stringology Conference 2014, PSC 2014

SP - 43

EP - 51

BT - Proceedings of the Prague Stringology Conference 2014, PSC 2014

A2 - Holub, Jan

A2 - Zd'arek, Jan

PB - Prague Stringology Club

T2 - 18th Prague Stringology Conference, PSC 2014

Y2 - 1 September 2014 through 3 September 2014

ER -