In this paper we study the enumeration and the construction, according to the number of ones, of particular binary words avoiding a fixed pattern. The growth of such words can be described by particular jumping and marked succession rules. This approach enables us to obtain an algorithm which constructs all binary words having a fixed number of ones and then kills those containing the forbidden pattern.
Pattern 1^j 0^i avoiding binary words / Bilotta, Stefano; Pergola, Elisa; Pinzani, Renzo. - In: ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE. - ISSN 2075-2180. - STAMPA. - 63:(2011), pp. 53-64. (Intervento presentato al convegno Words 2011 tenutosi a Praga, Rep. Ceca nel 12/09/2011 - 16/09/2011) [10.4204/EPTCS.63.9].
Pattern 1^j 0^i avoiding binary words
BILOTTA, STEFANO;PERGOLA, ELISA;PINZANI, RENZO
2011
Abstract
In this paper we study the enumeration and the construction, according to the number of ones, of particular binary words avoiding a fixed pattern. The growth of such words can be described by particular jumping and marked succession rules. This approach enables us to obtain an algorithm which constructs all binary words having a fixed number of ones and then kills those containing the forbidden pattern.
| File | Dimensione | Formato | |
|---|---|---|---|
|
final_version_words11.pdf
Accesso chiuso
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
150.12 kB
Formato
Adobe PDF
|
150.12 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
