Gray codes for \(A\)-free strings (Q1918874)

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\).