2017/08/22 by F. Blanchet-Sadri, Kun Chen, Kenneth Hawes
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.252.9
published as EPTCS 252, 2017, pp. 56-70 · In Proceedings AFL 2017, arXiv:1708.06226
arxiv created 2017/08/22 · arxiv updated 2017/08/23
We use results on Dyck words and lattice paths to derive a formula for the exact number of binary words of a given length with a given minimal abelian border length, tightening a bound on that number from Christodoulakis et al. (Discrete Applied Mathematics, 2014). We also extend to any number of distinct abelian borders a result of Rampersad et al. (Developments in Language Theory, 2013) on the exact number of binary words of a given length with no abelian borders. Furthermore, we generalize these results to partial words.