In this paper we propose an algorithm to generate binary words with no more 0's than 1's having a fixed number of 1's and avoiding the sequence for any fixed . Any binary word can be represented as a path on the Cartesian plane by associating a rise step, defined by (1,1), with each bit 1 in and a fall step, defined by (1,-1), with each bit 0 in . Given a path with n rise steps associated with the binary word avoiding the sequence , we generate a given number of paths with n+h rise steps, 1  h  j, avoiding the same sequence, by means of constructive rules. The number and the shape of the generated paths depend on the ordinate k of the endpoint of and on its suffix. We will prove that this generation is exhaustive, that is, all binary words with n bit 1 and avoiding the sequence are generated.

An algorithm for the Exhaustive Generation of Binary Words avoiding up-down Sequences / Stefano, Bilotta; Elisabetta, Grazzini; Elisa, Pergola. - In: AMERICAN REVIEW OF MATHEMATICS AND STATISTICS. - ISSN 2374-2348. - STAMPA. - 3:(2015), pp. 9-21. [10.15640/arms.v3n1a2]

An algorithm for the Exhaustive Generation of Binary Words avoiding up-down Sequences

BILOTTA, STEFANO;GRAZZINI, ELISABETTA;PERGOLA, ELISA
2015

Abstract

In this paper we propose an algorithm to generate binary words with no more 0's than 1's having a fixed number of 1's and avoiding the sequence for any fixed . Any binary word can be represented as a path on the Cartesian plane by associating a rise step, defined by (1,1), with each bit 1 in and a fall step, defined by (1,-1), with each bit 0 in . Given a path with n rise steps associated with the binary word avoiding the sequence , we generate a given number of paths with n+h rise steps, 1  h  j, avoiding the same sequence, by means of constructive rules. The number and the shape of the generated paths depend on the ordinate k of the endpoint of and on its suffix. We will prove that this generation is exhaustive, that is, all binary words with n bit 1 and avoiding the sequence are generated.
2015
3
9
21
Stefano, Bilotta; Elisabetta, Grazzini; Elisa, Pergola
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.

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