Donatella Merlini and Massimo Nocentini, 2018. Algebraic Generating Functions for Languages Avoiding Riordan Patterns. In Journal of Integer Sequences, vol. 21, pp. 18.1.3.
Abstract: We study the languages 𝔏𝔭 ⊂ {0,1}* of binary words w avoiding a given pattern 𝔭 such that |w|0 ≤ |w|1 for every w ∈ 𝔏𝔭, where |w|0 and |w|1 correspond to the number of 0-bits and 1-bits in the word w, respectively. In particular, we concentrate on patterns 𝔭 related to the concept of Riordan arrays. These languages are not regular, but can be enumerated by algebraic generating functions corresponding to many integer sequences that were previously unlisted in the On-Line Encyclopedia of Integer Sequences. We give explicit formulas for these generating functions expressed in terms of the autocorrelation polynomial of 𝔭, and also give explicit formulas for the coefficients of some particular patterns, algebraically and combinatorially.