In this paper we give a combinatorial interpretation of linear recurrences having constant coefficients. In particular, we describe a recursive construction for a language L such that the words of L having length n satisfy the given recurrence and avoid a cross-bifix-free set of patterns.
Pattern Avoiding Languages and Recurrence Relations Interpretation / Bilotta, Stefano; Grazzini, Elisabetta; Pergola, Elisa. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - STAMPA. - 156:(2017), pp. 1-19. [10.3233/FI-2017-1595]
Pattern Avoiding Languages and Recurrence Relations Interpretation
Bilotta, Stefano;Grazzini, Elisabetta
;Pergola, Elisa
2017
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 L such that the words of L having length n satisfy the given recurrence and avoid a cross-bifix-free set of patterns.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
