We consider some Riordan arrays related to binary words avoiding a pattern p, which can be easily studied by means of an A-matrix rather than their A-sequence. Both concepts allow us to define every element as a linear combination of other elements in the array; the A-equence is unique and corresponds to a linear dependence from the previous row. The A-matrix is not unique and corresponds to a linear dependence from several previous rows. However, for the problems considered in the present paper, we show that the A-matrix approach is more convenient. We provide explicit algebraic generating functions for these Riordan arrays and obtain many statistics on the corresponding languages. We thus obtain a deeper insight of the languages L([p]) of binary words avoiding p having a number of Os less or equal to the number of 1s.
Algebraic aspects of some Riordan Arrays related to binary words avoiding a pattern / D. Merlini; R. Sprugnoli. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 412:(2011), pp. 2988-3001. [10.1016/j.tcs.2010.07.019]
Algebraic aspects of some Riordan Arrays related to binary words avoiding a pattern
MERLINI, DONATELLA;SPRUGNOLI, RENZO
2011
Abstract
We consider some Riordan arrays related to binary words avoiding a pattern p, which can be easily studied by means of an A-matrix rather than their A-sequence. Both concepts allow us to define every element as a linear combination of other elements in the array; the A-equence is unique and corresponds to a linear dependence from the previous row. The A-matrix is not unique and corresponds to a linear dependence from several previous rows. However, for the problems considered in the present paper, we show that the A-matrix approach is more convenient. We provide explicit algebraic generating functions for these Riordan arrays and obtain many statistics on the corresponding languages. We thus obtain a deeper insight of the languages L([p]) of binary words avoiding p having a number of Os less or equal to the number of 1s.File | Dimensione | Formato | |
---|---|---|---|
r34.pdf
Accesso chiuso
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
282.97 kB
Formato
Adobe PDF
|
282.97 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.