Pattern Avoiding Languages and Recurrence Relations Interpretation

Article type: Research Article

Authors: Bilotta, Stefano | Grazzini, Elisabetta^{; *} | Pergola, Elisa

Affiliations: Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65 – 50134 Firenze, Italy. [email protected], [email protected], [email protected]

Correspondence: [*] Address for correspondence: Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze. Viale G.B. Morgagni 65 – 50134 Firenze, Italy.

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.

Keywords: Linear recurrence relations, Succession rules, Cross-bifix-free sets, Pattern avoidance

DOI: 10.3233/FI-2017-1595

Journal: Fundamenta Informaticae, vol. 156, no. 1, pp. 1-19, 2017