Pattern Avoiding Languages and Recurrence Relations Interpretation

Abstract

In this paper we give a combinatorial interpretation of linear recurrences having constant coefficients. In particular, we describe a recursive construction for a language ℒ such that the words in ℒ having length n satisfy the given recurrence and avoid a cross-bifix-free set of patterns.