\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Matthew B. Squire, Gray Codes for A-Free Strings

For any $q \geq 2$, 
let $\Sigma_{q}=\{0,\ldots,q\!-\!1\}$,
and fix a string $A$ over $\Sigma_{q}$.
The {\it $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 strings of length $n$ is prohibited by a parity
problem.
Our parity argument uses techniques similar to those
of Guibas and Odlyzko ({\it Journal of Combinatorial Theory A} 
30 (1981) pp.\ 183--208) 
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$.



\bye