% !TEX root = kFKM.tex

\subsection{Constructing de Bruijn Sequences}

Let $\TUPLES{n}{k}$ be the set of $k$-ary strings of length $n$.
For example, $$\TUPLES{2}{3} = \{11, 12, 13, 21, 22, 23, 31, 32, 33\}.$$
A \emph{de Bruijn sequence} for $\TUPLES{n}{k}$ is a sequence of length $k^n$ that contains each string in $\TUPLES{n}{k}$ exactly once as a substring when the sequence is viewed circularly.

Martin showed that a de Bruijn sequence for $\TUPLES{n}{k}$ can be constructed by a simple greedy algorithm in 1934 \cite{MartinM:1934}.
The algorithm starts with sequence $k^{n-1}$ (where exponentiation denotes repetition) and then repeatedly applies the following~rule:
%
\begin{quote}
\emph{Append the smallest symbol in $\{1, 2, \ldots, k\}$ so that substrings of length $n$ in the resulting linear sequence are distinct.} %when the sequence is viewed linearly.}
\end{quote}
%
As an example, let us illustrate one step of the algorithm when $n=2$ and $k=3$.
After applying the rule a handful of times, the partial sequence is $31121\underline{ \ }$.
At this point, the algorithm does not append $1$ since $1\underline{1}$ already appears in the sequence.
Similarly, $2$ is not appended since $1\underline{2}$ already appears.
However, $3$ can be appended and so the algorithm continues with the sequence $311213\underline{ \ }$.
Martin proved that the algorithm always terminates with a sequence that has length $k^n +  n -1$ and suffix $k^n$, and that a de Bruijn sequence is obtained by removing the initial $k^{n-1}$ prefix.
In particular, when $n=2$ and $k=3$, the algorithm terminates with $3112132233$ and so $112132233$ is a de Bruijn sequence for $\TUPLES{2}{3}$.
We mention that the choice of the initial sequence is critical to the success of Martin's algorithm.
For example, the greedy algorithm for $n=2$ and $k=3$ will get stuck after generating $112131$ if the initial sequence is the empty string $\epsilon$ or the single symbol $1$.
%
Knuth refers to Martin's sequence as the \emph{grand-daddy de Bruijn sequence}~\cite{opac-b1101743}.

The general term for these sequences is named after de Bruijn who showed that there are $2^{2^{n-1}-n}$ such sequences for $\TUPLES{n}{2}$ in 1946 \cite{deBruijn1}, and $(k!)^{k^{n-1}} k^{-n}$ for $\TUPLES{n}{k}$ in joint work with Aardenne-Ehrenfest in 1951 \cite{DeBruijn:51}.
Later detective work by Stanley revealed that Flye Sainte-Marie proved the same formula for $k=2$ in 1894 \cite{deBruijn2,FlyeSainteMarie:94}.

Martin's greedy algorithm is easy to implement, but it is impractical when $n$ is large since it requires $\Omega(k^n)$-space.
Fredricksen and Kessler \cite{Fredricksen19701,Fredricksen1975192,FKM2} (for $k=2$) and later Fredricksen and Maiorana \cite{FKM1} (for $k \geq 2$) provided a beautiful alternative that
generates each character in $O(1)$-amortized time and uses only $O(n)$ space.
Their construction is known as the \emph{FKM algorithm} and can be summarized as follows:
\begin{quote}
\emph{Concatenate the aperiodic prefixes of the necklaces in $\TUPLES{n}{k}$ in lexicographic order.}
\end{quote}
A \emph{necklace} is the lexicographically smallest string in an equivalence class of strings under rotation, and its \emph{aperiodic prefix} is the shortest prefix that can be repeated to create the string.
For example, the necklaces in $\TUPLES{2}{3}$ are 11, 12, 13, 23, 33 and thus the FKM algorithm creates the following sequence
%
\begin{equation*}
%\FKM{\TUPLES{2}{3}} = 
1 \cdot 1 2 \cdot 1 3 \cdot 2 \cdot 2 3 \cdot 3 = 112132233,% \text{ has substrings } 11,12,21,13,32,22,23,33,31.
\end{equation*}
where $\cdot$ denotes concatenation.
Interestingly, the FKM algorithm always generates the same sequence as Martin's algorithm and this sequence is the lexicographically smallest de Bruijn cycle for $\TUPLES{n}{k}$ (see Knuth's discussion in~\cite{opac-b1101743}).
The efficiency of the FKM algorithm was fully analyzed by Ruskey, Savage, and Wang \cite{Ruskey_Wang1}.

%We note that the FKM algorithm is usually defined in a slightly differ manner.
We note that the FKM algorithm can also be  described in a slightly different, but equivalent manner.
The \emph{period} of a string is the length of its aperiodic prefix.
A string is \emph{aperiodic} if its period equals its length.
An aperiodic necklace is a \emph{Lyndon word}.
The FKM algorithm can be defined as the lexicographic concatenation of the $k$-ary Lyndon words whose length divides $n$.
We will use the necklace definition because it is better suited for generalizations, as pointed out by Ruskey, Sawada, Williams \cite{Ruskey_bubble2}.

%Removed by referee's suggestion.
%Besides the greedy algorithm and the FKM algorithm, another classic construction of de Bruijn sequences is the linear-feedback shift register approach pioneered by Golomb \cite{golomb1982shift}.
%One drawback of this approach is its reliance on primitive polynomials over $\mathbb{GF}(k)$ with highest degree $n$; there is no general algorithm known for constructing these polynomials.


\subsection{Constructing Universal Cycles}

Given a set of strings $\mathbf{S} \subseteq \TUPLES{n}{k}$, a \emph{universal cycle} for $\mathbf{S}$ is a sequence of length $|\mathbf{S}|$ that contains each string in $\mathbf{S}$ exactly once as a substring when the sequence is viewed circularly.
For example, the subset $\mathbf{S_1} \subseteq \TUPLES{4}{3}$ of strings that have sum at least $10$ is
\begin{equation*}
%\scriptsize
\mathbf{S_1} = \{1333{,}2233{,}2323{,}2332{,}2333{,}3133{,}3223{,}3232{,}3233{,}3313{,}3322{,}3323{,}3331{,}3332{,}3333\}
\end{equation*}
and the lexicographically smallest universal cycle for $\mathbf{S_1}$ is
\[
 133322332323333.
\]
%
This natural generalization of de Bruijn sequences for $\TUPLES{n}{k}$ to subsets of $\TUPLES{n}{k}$ was introduced by Chung, Diaconis, and Graham in 1992 \cite{Chung:1992:UCC:162061.162067}.
Since that time universal cycles have been proven to exist for subsets of $\TUPLES{n}{k}$ that represent a variety of combinatorial objects including permutations, partitions, subsets, multisets, labeled graphs, various functions, and more~\cite{godbole1,brockman,Chung:1992:UCC:162061.162067,journals/algorithmica/HolroydRW12,hurlbert,jackson,johnson,opac-b1101743,godbole2,williams9,Ruskey2012155,Stevens20095255}. 
%Typically done using the well-known bijection between universal cycles and de Bruijn graphs (see Section \ref{sec:existProof}.

%Universal cycles have been shown to exist for a wide array of combinatorial objects~\cite{Chung:1992:UCC:162061.162067} although not always using the standard string encoding.  For example, there does not exist a universal cycle for permutations using the standard one-line notation. However,  they do exist when using alternate representations as demonstrated by Johnson~\cite{johnson}, and Ruskey, Holroyd, and Williams~\cite{journals/algorithmica/HolroydRW12}.  As an illustration for the latter, $123132$ is a universal cycle for ``shorthand'' permutations for $n=3$ since its substrings of length two are 12, 23, 31, 13, 32, 21 and each map to a distinct permutation by appending the unique missing symbol.

Given a specific set of strings $\mathbf{S} \subseteq \TUPLES{n}{k}$, the problem of finding an explicit construction (and generation algorithm) for a universal cycle for $\mathbf{S}$ is generally a more difficult problem than proving that one exists.
The approach considered in this article is to generalize the greedy algorithm and the FKM algorithm.
Previous results using this approach include the following:
\begin{itemize}
\item Moreno proved that a generalized FKM algorithm creates universal cycles for the set of rotations of the lexicographically largest $i$ necklaces \cite{IOPORT.02107234}.
\item Au proved that generalized FKM and greedy algorithm create universal cycles for the aperiodic strings in $\TUPLES{n}{k}$ \cite{lexi-smallest-aperiodic}.
\item The authors proved that generalized FKM and greedy algorithm create universal cycles for the binary strings with sum at least $s$ \cite{lexi-smallest}.
\end{itemize}
We will see that all three of these results can be explained using the same generalization of the FKM algorithm and the same generalization of the greedy algorithm.
To illustrate how these unified generalizations work, let us reconsider the strings $\mathbf{S_1}$ in $\TUPLES{4}{3}$ with sum at most $10$.   
Let the necklaces of a set $\mathbf{S}$ be denoted by $\mathbf{N}(\mathbf{S})$.  
Then 
\[ 
\mathbf{N}(\mathbf{S_1}) = \{1333, 2233, 2323, 2333, 3333\},
\]
and the concatenation of their aperiodic prefixes in lexicographic order gives
\[
 1333 \cdot 2233 \cdot 23 \cdot 2333 \cdot 3.
\]
This is identical to the lexicographically smallest universal cycle for $\mathbf{S_1}$ that we saw earlier.
More broadly, the generalized version of the FKM algorithm is stated below:
\begin{quote}
\emph{Concatenate the aperiodic prefixes of the necklaces in $\mathbf{S}$ in lexicographic order.}
\end{quote}
%As illustrated above, the generalized FKM algorithm successfully creates a universal cycle for $\mathbf{S}$ in \eqref{eq:sum10}.
Notice that the previous FKM results use $\mathbf{S} \subseteq \TUPLES{n}{k}$ that are \emph{closed under rotation}, meaning $\alpha \beta \in \mathbf{S}$ implies $\beta \alpha \in \mathbf{S}$.
To understand this fact, let $\Rotate{\mathbf{S}}$ denote closure of $\mathbf{S}$ under rotation.
Note that the number of distinct rotations of an individual string is equal to its period.
For example, $\Rotate{\{2233\}} = \{2233, 2332, 3322, 3223\}$ and $\Rotate{\{2323\}} = \{2323,3232\}$.
In other words, the length of the aperiodic prefix of $\alpha \in \TUPLES{n}{k}$ is equal to $|\Rotate{\alpha}|$.
Thus, the FKM algorithm creates sequences of the correct length for each $\mathbf{S}$ that is closed under rotation.

Generalizing the greedy algorithm is a bit more subtle due to the choice of the initial sequence.
In this article we will be focused on $\mathbf{S} \subseteq \TUPLES{n}{k}$ that are guaranteed to have $k^n \in \mathbf{S}$ (or $x \, k^{n-1} \in \mathbf{S}$ for some $x < k$).
Thus, $k^{n-1}$ remains a reasonable choice for the initial sequence.
Martin's algorithm is then generalized as follows
\begin{quote}
\emph{Append the smallest symbol in $\{1, 2, \ldots, k\}$ so that substrings of length $n$ in the resulting linear sequence are distinct and in $\mathbf{S}$.} %when the sequence is viewed linearly.}
\end{quote}
If we apply this greedy algorithm to $\mathbf{S_1}$, then it terminates with sequence 
\[ 333133322332323333
\] and removing initial $333$ results in the same universal cycle as generated by the generalized FMK approach.

Universal cycles have also been constructed using alternate approaches.
For example, Ruskey and Williams \cite{williams9} and later Holroyd, Ruskey, and Williams \cite{journals/algorithmica/HolroydRW12} provided an efficient algorithm to construct universal cycles for $\TUPLES{n{-}1}{n}$.
The authors also constructed universal cycles for binary strings of length $n$ whose sum falls within a given range \cite{universalcyclerange} which extends \cite{Ruskey_bubble2} and Stevens and Williams \cite{CoolestBinaryStrings}.


\subsection{New Results and Their Significance}

We prove that the generalized FKM and greedy algorithms generate a wide variety of natural universal cycles.
A list of examples appear in Sections \ref{sec:examples_first}--\ref{sec:examples_last} and it includes the aforementioned results by Moreno \cite{IOPORT.02107234}, Au \cite{lexi-smallest-aperiodic}, and the authors \cite{lexi-smallest}.
Furthermore, each of our examples follows from a single general result.  %which also applies to our example in \eqref{eq:sum10}--\eqref{eq:uniSum10}.

\begin{theorem} \label{thm:main}
The greedy and FKM algorithms create the lexicographically smallest universal cycle for any $\mathbf{S} \subseteq \TUPLES{n}{k}$ that satisfies the following closure properties:
\begin{enumerate}
\item[(C1)] \emph{The set of strings $\mathbf{S}$ is closed under rotation.} %\\
%For example, $1333 \in \mathbf{S}$ implies that $3133, 3313, 3331 \in \mathbf{S}$.
\item[(C2)] \emph{Its subset of necklaces is closed under replacing any suffix of length $i$ by~$k^i$.} %\\
%For example, $2323 \in \mathbf{N}$ implies that $2333, 3333 \in \mathbf{N}$.
\end{enumerate}
\end{theorem}

%We let $\CLASS{n}{k} \subseteq 2^{\TUPLES{n}{k}}$ be the set of tuples subsets that satisfy these two closure properties.
%A set $\mathbf{S}$ is \emph{closed under rotation} if $\alpha \beta \in \mathbf{S}$ implies $\beta \alpha \in \mathbf{S}$.
%This closure property is very natural when considering the FKM algorithm. % as discussed in Section \ref{sec:FKM}.
%As mentioned earlier, the first closure property is very natural when considering the FKM algorithm.
%However, it is not sufficient for guaranteeing the existence of universal cycles.
We note that the first closure property is not sufficient for guaranteeing the existence of universal cycles.
For example, $\{11,22\}$ is closed under rotation and has no universal cycle.
Our second closure property is also insufficient for proving the existence.
For example, $\{11,12, 22\} \subseteq \TUPLES{2}{2}$ does not have a universal cycle.

To underscore the significance of our results, we note that the greedy algorithm, the FKM algorithm, and the lexicographically smallest universal cycle do not always operate in such harmony.
For example, the subset $\mathbf{S_2} \subset \TUPLES{3}{3}$ that does not have $13$ as a cyclic substring is 
\begin{equation*}
\mathbf{S_2} = \{111{,}112{,}121{,}122{,}123{,}211{,}212{,}221{,}222{,}223{,}231{,}232{,}233{,}312{,}322{,}323{,}332{,}333\}.
\end{equation*}
In other words, $\mathbf{S_2}$ does not have strings in the form $13x$, $x13$, or $3x1$.
Clearly $\mathbf{S_2}$ is closed under rotation, so it satisfies our first condition.
The necklaces in $\mathbf{S_2}$ are
\[
\mathbf{N}(\mathbf{S_2})  = \{111, 112, 122, 123, 222, 223, 233, 333\}.
\]
Notice that  $\mathbf{N}(\mathbf{S_2})$ does not satisfy our second closure property since $111$ is included but $113$ is not.
Thus, our results do not guarantee that the FKM algorithm will create a universal cycle for $\mathbf{S_2}$.
In fact, the FKM algorithm creates
\[
1 \cdot 112 \cdot 122 \cdot 123 \cdot 2 \cdot 223 \cdot 233 \cdot 3. % = 111212212322232333.
\]
This is not a universal cycle for $\mathbf{S_2}$ since $211$ and $312$ do not appear, while $212$ appears twice and $311$ appears when it should not.
On the other hand, the greedy algorithm applied to $\mathbf{S_2}$ creates 
\[
221112122231232233,
\]
which is a universal cycle for $\mathbf{S_2}$.
However, it is not the lexicographically smallest universal cycle for $\mathbf{S_2}$ (when viewed linearly). % which is its rotation $111212223123223322$.
%On the other hand, our results do hold whenever the avoided cyclic substring does not contain the symbol $k$.

The previous example showed that the harmony produced the greedy algorithm, the FKM algorithm, and the lexicographically smallest universal cycle does not hold for the strings in $\TUPLES{3}{3}$ that avoid $13$ as a cyclic substring.
Notice that in this case the avoided substring $13$ contains the symbol $k=3$.
We will see in Section \ref{sec:examples_substring} that the three interrelated results do hold when the avoided substring does not contain the symbol $k$.
This illustrates one way in which our result is `tight'.

%Can your find an example where greedy works and is not lex smallest even up to rotation????
%We will also demonstrate the `tightness' of our results with some non-existence results.

One motivation for constructing universal cycles is so that they can be used in applications. 
Without an explicit construction it can be computationally infeasible to create these sequences when $n$ is large.
Sample applications of de Bruijn sequences include dynamic connections in overlay networks~\cite{gauron}, genomics~\cite{genomics}, software calculation of the ruler function in computer words~\cite{opac-b1101743}, and indexing a $1$ in a computer word~\cite{Leiserson}.
Our two-pronged results have an additional benefit: Those in need of one of our universal cycles can start by implementing the simple greedy algorithm; if this proves to be infeasible due to memory constraints, then they can implement the FKM algorithm.
%Furthermore, the implementations for the various examples discussed in this article will all bear strong similarity to each other, and thus reduce the difficulty of implemented them.
%The authors have begun to explore highly-efficient implementations for our results in a subsequent article (\noteQuestion{WADS paper?}). 
De Bruijn sequences are also used as education tools (see Graham, Knuth, and Patashnik's \emph{Concrete Mathematics} \cite{Concrete}) and are involved in many interesting academic papers (for recent examples, see Levine \cite{Levine} and Ehrenborg, Kitaev, and Steingr\'{\i}mmson \cite{Ehrenborg}). 
%Mykkeltveit \cite{Mykkeltveit197240}

To conclude our introduction we mention that our second closure property can be slightly relaxed to allow $k^n \notin \mathbf{S}$.
For example, the constructions for $\mathbf{S_1}$ still work when $k^n$ is omitted from $\mathbf{S_1}$ and the final $k$ is omitted from the universal cycles generated.
We use this minor generalization when considering periodic and aperiodic strings.
%One limitation of our second closure property is that it forces $k^n \in \mathbf{S}$, and we would like flexibility to exclude it for certain results.
%It turns out that the classic algorithms still work when $k^n$ is excluded.
%For example, consider our previous examples in \eqref{eq:sum10} and \eqref{eq:uniSum10}.
%We state this fact in the following remark and will justify it later.
%The second closure property gives us enough leverage to prove that the FKM and greedy algorithms both work.
%The second closure property ensures that a universal cycle for $\mathbf{S}$ exists (see Section \ref{sec:exist}) and gives us enough leverage to prove that the FKM and greedy algorithms work.
%Also ensures that $k^n \in \mathbf{S}$ which justifies our choice of initial sequence. 
%(A comment on excluding $k^n$ appears elsewhere)

\begin{corollary} \label{cor:kn}
Theorem \ref{thm:main} holds if $\mathbf{S} \cup \{k^n\} \subseteq \TUPLES{n}{k}$ satisfies (C1) and (C2).
\end{corollary}

The main results of this paper are also found in Wong's PhD thesis~\cite{WongThesis}.


\subsection{Outline}

The remainder of this paper is organized as follows.
Section~\ref{sec:definitions} investigates our second closure property under the name $k$-suffix languages.
Section~\ref{sec:examples} proves that the universal cycles discussed in Theorem \ref{thm:main} exist, and gives a list of specific universal cycles that are constructed by it.
Section~\ref{sec:FKM} proves our result on the FKM algorithm.
Section~\ref{sec:greedy} proves our result on the greedy algorithm and proves that our universal cycles are lexicographically smallest.
%Section \ref{sec:alg} provides an algorithm to generate universal cycles of these sets. % and provides an algorithm to generate them.
Section~\ref{sec:final} concludes the paper with open problems and remarks.

