Dyck Words, Lattice Paths, and Abelian Borders

F. Blanchet-Sadri
(Department of Computer Science, University of North Carolina)
Kun Chen
(Department of Computer Science, University of North Carolina)
Kenneth Hawes
(Department of Mathematics, University of Virginia)

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.

In Erzsébet Csuhaj-Varjú, Pál Dömösi and György Vaszil: Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science 252, pp. 56–70.
Published: 21st August 2017.

ArXived at: http://dx.doi.org/10.4204/EPTCS.252.9 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org