Abelian borders in binary words

In this article we study the appearance of abelian borders in binary words, a notion closely related to the abelian period of a word. We show how many binary words have shortest border of a given length by identifying relations with Dyck words. Furthermore, we give some bounds on the number of abelian border-free words of a given length and on the number of abelian words of a given length that have at least one abelian border. Finally, using some techniques employed in a recent paper by Christodoulakis et al. (2013), we show that there exists an algorithm that finds the shortest abelian border of a binary word that is not abelian border-free in Θ(n) time on average.