Starting from a succession rule for Catalan numbers, we define a procedure for encoding and listing the objects enumerated by these numbers such that two consecutive codes of the list differ only by one digit. The Gray code we obtain can be generalized to all the succession rules with the stability property: each label k has in its productions two labels c1 and c2, always in the same position, regardless of k. Because of this link, we define Gray structures as the sets of those combinatorial objects whose construction can be encoded by a succession rule with the stability property. This property is a characteristic that can be found among various succession rules, such as the finite, factorial or transcendental ones. We also indicate an algorithm which is a very slight modification of Walsh's one, working in O(1) worst-case time per word for generating Gray codes.

A GENERAL EXHAUSTIVE GENERATION ALGORITHM FOR GRAY STRUCTURES / A. BERNINI; E. GRAZZINI; E. PERGOLA; R. PINZANI. - In: ACTA INFORMATICA. - ISSN 0001-5903. - STAMPA. - 44(5):(2007), pp. 361-376. [10.1007/s00236-007-0053-0]

A GENERAL EXHAUSTIVE GENERATION ALGORITHM FOR GRAY STRUCTURES

BERNINI, ANTONIO;GRAZZINI, ELISABETTA;PERGOLA, ELISA;PINZANI, RENZO
2007

Abstract

Starting from a succession rule for Catalan numbers, we define a procedure for encoding and listing the objects enumerated by these numbers such that two consecutive codes of the list differ only by one digit. The Gray code we obtain can be generalized to all the succession rules with the stability property: each label k has in its productions two labels c1 and c2, always in the same position, regardless of k. Because of this link, we define Gray structures as the sets of those combinatorial objects whose construction can be encoded by a succession rule with the stability property. This property is a characteristic that can be found among various succession rules, such as the finite, factorial or transcendental ones. We also indicate an algorithm which is a very slight modification of Walsh's one, working in O(1) worst-case time per word for generating Gray codes.
2007
44(5)
361
376
A. BERNINI; E. GRAZZINI; E. PERGOLA; R. PINZANI
File in questo prodotto:
File Dimensione Formato  
Acta 2007.pdf

Accesso chiuso

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