Counting and Verifying Abelian Border Arrays of Binary Words

10/30/2021

∙

by   Mursalin Habib, et al.

∙

0

∙

share

In this note, we consider the problem of counting and verifying abelian border arrays of binary words. We show that the number of valid abelian border arrays of length n is 2^n-1. We also show that verifying whether a given array is the abelian border array of some binary word reduces to computing the abelian border array of a specific binary word. Thus, assuming the word-RAM model, we present an O(n^2/log^2n) time algorithm for the abelian border array verification problem.