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.
2011
412
2988
3001
D. Merlini; R. Sprugnoli
File in questo prodotto:
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.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/395927
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 14
social impact