In this paper we study the construction and the enumeration of binary words having more 1's than 0's and avoiding a set of cross-bifix-free patterns. We give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words having more 1's than 0's and then kills those containing the forbidden patterns. Finally, we give the generating function of such words according to the number of ones.

Avoiding cross-bifix-free binary words / Stefano Bilotta; Elisabetta Grazzini; Elisa Pergola; Renzo Pinzani. - In: ACTA INFORMATICA. - ISSN 0001-5903. - STAMPA. - 50:(2013), pp. 157-173. [10.1007/s00236-013-0176-4]

Avoiding cross-bifix-free binary words

BILOTTA, STEFANO;GRAZZINI, ELISABETTA;PERGOLA, ELISA;PINZANI, RENZO
2013

Abstract

In this paper we study the construction and the enumeration of binary words having more 1's than 0's and avoiding a set of cross-bifix-free patterns. We give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words having more 1's than 0's and then kills those containing the forbidden patterns. Finally, we give the generating function of such words according to the number of ones.
2013
50
157
173
Stefano Bilotta; Elisabetta Grazzini; Elisa Pergola; Renzo Pinzani
File in questo prodotto:
File Dimensione Formato  
Acta 13 on line.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 729.73 kB
Formato Adobe PDF
729.73 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/787541
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact