Gray codes for \(A\)-free strings
type: Item
instance of: scholarly article
title: Gray codes for \(A\)-free strings
zbMATH Open document ID: 0849.94021
author: Matthew B. Squire
published in: The Electronic Journal of Combinatorics
publication date: 1996-07-21T00:00:00Z
full work available at URL: https://eudml.org/doc/118904
full work available at URL: R17
review text: Summary: For any \(q\geq 2\), let \(\Sigma_q= \{0, 1, \dots, q-1\}\), and fix a string \(A\) over \(\Sigma_q\). The \(A\)-free strings of length \(n\) are the strings in \(\Sigma_q^n\) which do not contain \(A\) as a contiguous substring. In this paper, we investigate the possibility of listing the \(A\)-free strings of length \(n\) so that successive strings differ in only one position, and by \(\pm 1\) in that position. Such a listing is a Gray code for the \(A\)-free strings of length \(n\). We identify those \(q\) and \(A\) such that, for infinitely many \(n\geq 0\), a Gray code for the \(A\)-free string of length \(n\) is prohibited by a parity problem. Our parity argument uses techniques similar to those of \textit{L. J. Guibas} and \textit{A. M. Odlyzko} [J. Comb. Theory, Ser. A 30, 183-208 (1981; Zbl 0454.68109)] who enumerated the \(A\)-free strings of length \(n\). When \(q\) is even, we also give the complementary positive result: for those \(A\) for which an infinite number of parity problems do not exist, we construct a Gray code for the \(A\)-free strings of length \(n\) for all \(n\geq 0\).
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 907638
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 907638