% !TEX root = kFKM.tex


Although the language $\CLASS{n}{k}$ includes a broad class of combinatorial objects, there are still sets that are not in $\CLASS{n}{k}$ while their universal cycles can be constructed by the FKM algorithm. 
As an example, consider the set $\mathbf{S_4} \subseteq \TUPLES{4}{3}$ which contains the following length 4 strings:
\begin{center}
1112, 1121, 1122, 1212, 1211, 1221, 1222, 1322, 2111,  \\ 
2112, 2121, 2122, 2132, 2211, 2212, 2213, 2221, 3221.
\end{center} 
The set $\mathbf{S_4}$ is closed under rotation, but $\mathbf{N}({\mathbf{S_4}}) = \{1112, 1122, 1212, 1222, $ $1322\}$ is not a $k$-suffix language. 
However, $\FKM{\mathbf{S_4}} = 1112 \cdot 1122 \cdot 12 \cdot 1222 \cdot 1322$ is a universal cycle for $\mathbf{S_4}$. 
Naturally, we would like to characterize the sets of strings $\mathbf{S}$ in which $\FKM{\mathbf{S}}$ is a universal cycle.
Similarly, we are interested in characterizing when the greedy algorithm works.  













%In this paper, we provide a framework to generate universal cycles for a broad class of $k$-ary strings. 
%The universal cycles can be generated greedily or by necklace concatenation, and they are the lexicographically least universal cycles for the sets. 

%In this paper, we provide a framework to generate universal cycles for sets in $\CLASS{n}{k}$. 
%We also provide an algorithm to generate universal cycles for these sets. 
%The universal cycles can be constructed by concatenating the aperiodic prefix of the necklaces in the set in lexicographic order. 
%They can also be constructed greedily, and are the lexicographically smallest universal cycles among the sets. 

\begin{comment}
We note that by interchanging the symbols $k$ with $i \in \{1, 2, \ldots, k-1\}$, we can further produce some new universal cycles for other combinatorial objects based on the universal cycles discussed in this paper. 
We can extend the universal cycles for $\mathbf{S}_2$, $\mathbf{S}_3$ and $\mathbf{S}_4$ in Section~\ref{sec:kSuffix} to construct universal cycles for the following sets respectively:
\begin{enumerate}[label=\roman*)]
\item Subsets of $\TUPLES{n}{k}$ with at least $\ell_i$ copies of $i \in \{1, 2, \ldots, k-1\}$; 
\item Subsets of $\TUPLES{n}{k}$ with at most $u_k$ copies of $k$; and
%\item Tuples that contain at most $u_1$ copies of $1$;
\item Subsets of $\TUPLES{n}{k}$ that circularly avoid substring $\beta \in \mathbf{C}^*$, where $\mathbf{C}$ is a $(k-1)$-subset of $\{1, 2, \ldots, k\}$.
%\item Tuples that do not have a specific period $q$ for $q < n$;
%\item that avoid rotations of periodic necklaces;
%\item that contain all rotations of the lexicographically largest $i$ necklaces; and
%\item that are union or intersection of any of the above.
%\item Between $n \cdot \lfloor \frac{i}{n} \rfloor$ and $n \cdot \lfloor \frac{i+1}{n} \rfloor$ tuples for any $1 \leq i \leq k^n$.
\end{enumerate}
As an example, consider the set $\mathbf{X} \subseteq \TUPLES{4}{3}$ that circularly avoids $\beta = 12 \in \{1, 2\}^*$, 
\begin{equation*}
\emph{FKM}(\mathbf{X}) = 1 113 132 133 2 223 233 3.
\end{equation*}
By interchanging the symbols $k =3$ and $i = 2$ in \emph{FKM}($\mathbf{X}$), we obtain a universal cycle for subset of $\TUPLES{4}{3}$ that avoids ``13": 111212312233323222.
%\begin{equation*}
%1 112 123 122 3 332 322 2.
%\end{equation*}



We conclude the paper with two remarks.
\begin{enumerate}
\item Although the language $\CLASS{n}{k}$ includes a broad class of combinatorial objects, there are still sets that are not in $\CLASS{n}{k}$ while their universal cycles can be constructed by the FKM algorithm. 
As an example, consider the set $\mathbf{S_4} \subseteq \TUPLES{4}{3}$ which contains the following length 4 strings:
\begin{center}
1112, 1121, 1122, 1212, 1211, 1221, 1222, 1322, 2111,  \\ 
2112, 2121, 2122, 2132, 2211, 2212, 2213, 2221, 3221.
\end{center} 
The set $\mathbf{S_4}$ is closed under rotation, but $\mathbf{N}({\mathbf{S_4}}) = \{1112, 1122, 1212, 1222, $ $1322\}$ is not a $k$-suffix language. 
However, $\FKM{\mathbf{S_4}} = 1112 \cdot 1122 \cdot 12 \cdot 1222 \cdot 1322$ is a universal cycle for $\mathbf{S_4}$. 
Naturally, we would like to characterize the sets of strings $\mathbf{S}$ in which $\FKM{\mathbf{S}}$ is a universal cycle.
Similarly, we are interested in characterizing when the greedy algorithm works.  
%A natural open problem is thus to explore a language $\mathbf{L}$ such that $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ {if and only if} $\mathbf{S} \in \mathbf{L}$. 

%\item This paper proves $\FKM{\mathbf{S}}$ and $\GREEDY{\mathbf{S}}$ produce the same universal cycle when $\mathbf{S} \in \CLASS{n}{k}$. 
%However, the algorithms do not always produce the same sequence. 
%As an example, consider the set $\mathbf{X} = \{111, 112, 121, 122, 123, $ $211, 212, 221, 222, 223, 231, 232, 233, 312, 322, 323, 332, 333\} \subseteq \TUPLES{3}{3}$. %that contains strings circularly avoid ``13". %Universal cycle for $\mathbf{X}$ can be constructed by the greedy algorithm.
%The sequence $\GREEDY{\mathbf{X}} = 221112122231232233$ is a universal cycle for $\mathbf{X}$, but $\FKM{\mathbf{X}} = 1 \cdot 112 \cdot 122 \cdot 123 \cdot 2 \cdot 223 \cdot 233 \cdot 3$ is not even a universal cycle for $\mathbf{X}$.
%The FKM algorithm, however, produces the sequence $1 \cdot 112 \cdot 122 \cdot 123 \cdot 2 \cdot 223 \cdot 233 \cdot 3$ which is not a universal cycle for the set with the string 311 which contains ``13" when considered cyclicly. 
%An interesting problem is therefore to investigate when $\GREEDY{\mathbf{S}}$ produces the same sequence as $\FKM{\mathbf{S}}$. Is there a language to include all sets $\mathbf{S}$ where $\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}}$? 


\medskip
\item The FKM construction also works for sets $\mathbf{S} \subseteq \TUPLES{n}{k}$ that are closed under rotation, and satisfy the following closure property:
\begin{quote}
%{If ${a_1 a_2 \cdots a_{n-1} x}\text{, } {b_1 b_2 \cdots b_{n-1}x}  \in \mathbf{S}$ are necklaces and ${a_1 a_2 \cdots a_{n-1}y} \in \mathbf{S}$ with $k \geq y > x$, then $b_1  b_2  \cdots  b_{n-1}  y  \in \mathbf{S}$}
If a string $a_1 a_2 \cdots a_{n-j} k^j \in \mathbf{S}$ is a necklace but not the lexicographically largest necklace, then $a_1 a_2 \cdots a_{n-j-1} k k^j \in \mathbf{S}$. 
\end{quote} 
This result generalizes the FKM portion of Corollary~\ref{cor:kn}, and a detailed proof is included in the third author's PhD thesis~\cite{WongThesis}.
%In fact, this language is a broader language than $\CLASS{n}{k}$ and admits sets that do not include $k^n$. 
%However, it does not lead to any interesting set other than those in $\CLASS{n}{k}$. 
%It would be interesting to generalize the language further to cover more interesting sets. 
%A detailed proof for generalizing the FKM algorithm to this language is currently under preparation and will be a part of the third author's PhD thesis.
%A detailed proof for generalizing the FKM algorithm to this language is currently under preparation and will be a part of the third author's PhD thesis.

%One future direction of this research is to further generalize the FKM construction to cover more interesting sets.

\end{enumerate}
\end{comment}

%\item Are there other interesting sets which are in $\CLASS{n}{k}$?
%\item Can universal cycles for all sets in $\CLASS{n}{k}$ be constructed in constant amortized time per symbol?
%\item Does universal cycles exist for the following sets? If so, can they be constructed efficiently?
%\begin{itemize}
%\item Subset of $\TUPLES{n}{k}$ that contains all strings with at least $\ell_i$ copies of $i$ for all $i \in \{1, 2, \ldots, k\}$;
%\item Subset of $\TUPLES{n}{k}$ that contains all strings with at most $u_i$ copies of $i$ for all $i \in \{1, 2, \ldots, k\}$; 
%\item Subset of $\TUPLES{n}{k}$ that contains all strings that circularly avoid substring $\beta \in \{1, 2, \ldots, k\}^*$; and
%\item Subset of $\TUPLES{n}{k}$ that contains all strings that are rotations of the lexicographically smallest $i$ necklaces.
%\end{itemize}
%\item Can FKM construction and Martin's greedy algorithm be extended to other languages?
%\item In~\cite{lexi-smallest}, the authors proved that universal cycles for binary strings with weight at least $w$ can be constructed in constant amortized time per bit. The result can be extended to construct universal cycles for subsets of $k$-ary strings of length $n$ (i) with sum at least $s$, (ii) with at least $\ell_k$ copies of $k$, and (iii) with at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$ in constant amortized time per bit. Since the number of Lyndon words is proportional to the number of prenecklace~\cite{DBLP:journals/siamcomp/RuskeyS99}, we can also say that universal cycles for $k$-ary strings of length $n$ that avoid periodic strings can be constructed in constant amortized time per bit. An open problem would be to find constant amortized time algorithms to generate universal cycles for other sets which are closed under rotation with their necklace sets $k$-suffix$k$-suffix langauge. 
