A cross-bifix-free set of words is a set in which no prefix of any length of any word is the suffix of any other word in the set. A construction of cross-bifix-free sets has recently been proposed within a constant factor of optimality. We propose a Gray code for these cross-bifix-free sets and a CAT algorithm generating it. Our Gray code list is trace partitioned, that is, words with zero in the same positions are consecutive in the list.

A Gray code for cross-bifix-free sets / Bernini, Antonio; Bilotta, Stefano; Pinzani, Renzo; Vajnovszki, Vincent. - In: MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE. - ISSN 0960-1295. - STAMPA. - 27:(2017), pp. 184-196. [10.1017/S0960129515000067]

A Gray code for cross-bifix-free sets

BERNINI, ANTONIO;BILOTTA, STEFANO;PINZANI, RENZO;
2017

Abstract

A cross-bifix-free set of words is a set in which no prefix of any length of any word is the suffix of any other word in the set. A construction of cross-bifix-free sets has recently been proposed within a constant factor of optimality. We propose a Gray code for these cross-bifix-free sets and a CAT algorithm generating it. Our Gray code list is trace partitioned, that is, words with zero in the same positions are consecutive in the list.
2017
27
184
196
Bernini, Antonio; Bilotta, Stefano; Pinzani, Renzo; Vajnovszki, Vincent
File in questo prodotto:
File Dimensione Formato  
GC_CBFS_submission.pdf

accesso aperto

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 269.96 kB
Formato Adobe PDF
269.96 kB Adobe PDF
a-gray-code-for-cross-bifix-free-sets.pdf

Accesso chiuso

Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 318.02 kB
Formato Adobe PDF
318.02 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/1008436
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact