\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
{\bf Ming-wei Wang and Jeffrey Shallit}
\medskip
\noindent
{\bf On Minimal Words With Given Subword Complexity}
\vskip.5cm


We prove that the minimal length of a word $S_n$ having the property
that it contains exactly $F_{m+2}$ distinct subwords of length $m$ for
$1 \leq m \leq n$ is $F_n + F_{n+2}$. Here $F_n$ is the $n$th Fibonacci
number defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n
> 2$. We also give an algorithm that generates a minimal word $S_n$ for
each $n \geq 1$.


\bye