% !TEX root = kFKM.tex

\title{\bf Generalizing the Classic Greedy and \\Necklace Constructions of\\ de Bruijn Sequences and Universal Cycles}

%\title[Generalizing Classic Constructions of de Bruijn Sequences]{Generalizing the Classic Greedy and Necklace Constructions of de Bruijn Sequences}
%\title{Generalizing the Classic Greedy and Lyndon Word de Bruijn Sequence Constructions}
%\title{A generalized universal cycle construction for a broad class of $k$-ary strings}% and $k$-suffix necklace property}
\author{
Joe Sawada\thanks{School of Computer Science, University of Guelph, Canada. Research supported by NSERC. \texttt{jsawada@uoguelph.ca}} 
 \and
Aaron Williams\thanks{ Division of Science, Mathematics, and Computing, Bard College at Simon`s Rock, USA. \texttt{haron@uvic.ca}} 
\and
Dennis Wong\thanks{Department of Mathematics, Computer Science, and Information Systems, Northwest Missouri State University, USA. \texttt{cwong@uoguelph.ca}}
}

\date{\dateline{Aug 26, 2015}{Jan 23, 2016}{Feb 5, 2016}\\
\small Mathematics Subject Classifications: 05A05, 05A15}

%\address{School of Computer Science, University of Guelph, Canada}

\maketitle


\begin{abstract}
We present a class of languages that have an interesting property:  For each language $\mathbf{L}$ in the class, both the classic greedy algorithm and the classic Lyndon word (or necklace) concatenation algorithm provide the lexicographically smallest universal cycle for $\mathbf{L}$.  The languages consist of length $n$ strings over $\{1,2,\ldots ,k\}$ that are closed under rotation with their subset of necklaces also being closed under replacing any suffix of length $i$ by $i$ copies of~$k$.     
Examples include all strings (in which case universal cycles are commonly known as de Bruijn sequences), strings that sum to at least $s$, strings with at most $d$ cyclic descents for a fixed $d>0$, strings with at most $d$ cyclic decrements for a fixed $d>0$, and strings avoiding a given period.  Our class is also closed under both union and intersection, and our results generalize results of several previous papers.
\end{abstract}


\begin{comment}

% Aaron's modified abstract for submission to Combinatorica.
\begin{abstract}
We present a class of languages that have an interesting property:  For every language $\mathbf{L}$, both the classic greedy algorithm and the classic Lyndon word (or necklace) concatenation provide the lexicographically smallest universal cycle for $\mathbf{L}$.  In other words, the $|\mathbf{L}|$ strings in $\mathbf{L}$ can be packed into a string of length $|\mathbf{L}|$ using well-known constructions.  (When $\mathbf{L}$ contains all $k$-ary strings of length $n$, the resulting universal cycle is commonly known as a de Bruijn sequence.)  The languages consist of length $n$ strings over $\{1,2,\ldots ,k\}$ that are closed under rotation with their subset of necklaces also being closed under replacing any suffix of length $i$ by $i$ copies of~$k$.     
Examples include all strings, strings that sum to at least $s$, strings with at most $d>0$ descents, strings with at most $d>0$ decrements, and strings avoiding a given period.  Our class is also closed under both union and intersection, and our results generalize several previous papers.
%\end{abstract}



% Joe's abstract for submission to Combinatorica.
%\begin{abstract}

\bigskip

We present a class $\CLASS{n}{k}$ of languages that have an interesting property:  For every $\mathbf{L} \in \CLASS{n}{k}$, both a standard greedy algorithm and a Lyndon word (or necklace) concatenation algorithm can be used to generate the lexicographically smallest universal cycle for  $\mathbf{L}$.
The languages consist of length $n$ strings over $\{1,2,\ldots ,k\}$ and each $\mathbf{L} \in \CLASS{n}{k}$  is  closed under rotation with its subset of necklaces also being closed under replacing any suffix of length $i$ by $i$ copies of~$k$.     
Examples include: all strings, strings that sum to at least $s$, and strings with at most $d>0$ descents or decrements, and strings avoiding a given period.  This class is closed under both union and intersection.
\end{abstract}

\begin{comment}
%=============
\begin{abstract}
The lexicographically smallest de Bruijn sequence for $k$-ary strings of length $n$ can be constructed using Martin's greedy algorithm (Bulletin of the American Mathematical Society, 40:859--864, 1934) or the necklace concatenation algorithm by Fredricksen, Kessler and Maiorana (Discrete Mathematics, 23:207--210, 1978).
We generalize their classic algorithms so that they generate universal cycles for other interesting sets.
Specific examples include the subsets of $k$-ary strings of length $n$ that
(i) have sum at least $s$;
(ii) have at least $\ell_k$ copies of $k$;
(iii) have at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$;
(iv) circularly avoid substring $\beta \in \{1, 2, \ldots, k-1\}^{*}$;
(v) are rotations of the lexicographically largest $i$ necklaces;
(vi) are not rotations of a given periodic necklace;
% or whose last symbol is $x < k$;
%(vi) are not rotations of a given necklace that doesn't have a suffix of the form $k^{j+1}$ that can be replaced by $x k^j$ and still be a necklace;
% (vi) are not rotations of a given necklace whose longest suffix of $k$s is fixed (ie cannot be modfied without creating a non-necklace); 
% (vi) are not rotations of a given necklace whose suffix of the form $x k^j$ with $x < k$ cannot be changed without creating a non-necklace;
and (vii) are unions and/or intersections of these sets. 
The last two results also provide universal cycles for subsets with strings that (viii) are periodic and (ix) have period in a given subset of $\{1,2,\ldots,n\}$ that contains $n$.
More broadly, our generalization applies to a subset of the $k$-ary strings of length $n$ if (a) it is closed under rotation, and (b) its subset of necklaces is closed under replacing any suffix of length $i$ by $i$ copies of~$k$.
\end{abstract}
%=============



\begin{comment}
\begin{abstract}
The lexicographically smallest de Bruijn sequence for the $n$-tuples of $\{1,2,\ldots,k\}$ can be constructed using Martin's greedy algorithm (Bulletin of the American Mathematical Society, 40:859--864, 1934) or the Lyndon word concatenation algorithm by Fredricksen, Kessler and Maiorana (Discrete Mathematics, 23:207--210, 1978).
We generalize their classic algorithms so that they generate universal cycles for many interesting subsets of tuples.
Specific examples include tuples that
(i) have sum at least $s$;
(ii) have at least $\ell_k$ copies of $k$;
(iii) have at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$;
(iv) circularly avoid substring $\beta \in \{1, 2, \ldots, k-1\}^{*}$;
(v) are rotations of the lexicographically largest $i$ necklaces;
(vi) are not rotations of a given periodic necklace;
and (vii) are unions and/or intersections of these sets. 
The last two results also provide universal cycles for tuples that (viii) are periodic; (ix) have period in $P \subseteq \{1,2,\ldots,n\}$ with $1 \in P$.
More broadly, our generalization applies to a subset of tuples if (a) its is closed under rotation, and (b) its subset of necklaces is closed under replacing any suffix of length $i$ by $i$ copies of~$k$.
\end{abstract}
\end{comment}








\begin{comment}
\begin{abstract}
%We provide a general framework to construct universal cycles for a broad class of $k$-ary strings. 
We generalize the famous necklace concatenation algorithm (FKM algorithm) by Fredricksen, Kessler and Maiorana to construct universal cycles for a broad class of $k$-ary strings.
Specific examples include subsets of $k$-ary strings of length $n$ that contains strings 
%
(i) with sum at least $s$;
(ii) with at least $\ell_k$ copies of $k$;
(iii) with at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$;
(iv) that circularly avoid substring $\beta \in \{1, 2, \ldots, k-1\}^{*}$;
(v) that are not rotations of a given periodic necklace;
(vi) that are rotations of the lexicographically largest $i$ necklaces;
and (vii) that are union or intersection of these sets.
%
%These sets $\mathbf{S}$ are closed under rotation.  Moreover, the necklaces of $\mathbf{S}$ yield a Gray code where successive necklaces differ by one symbol when listed in lexicographic order. 
%$a_1 a_2 \cdots (a_{n-j}+1) \in \mathbf{S}$, $a_1 a_2 \cdots (a_{n-j}-1) \in \mathbf{S}$  %then $a_1  a_2  \cdots  a_{n-i}  k^{i}  \in \mathbf{S}$ for all $0 \leq i \leq n$.
A $k$-suffix language $\mathbf{K}$ is a subset of $k$-ary strings of length $n$ that satisfies a simple closure property: If $a_1  a_2  \cdots  a_{n} \in \mathbf{K}$, then $a_1  a_2  \cdots  a_{n-i}  k^{i}  \in \mathbf{K}$ for all $1 \leq i \leq n$.
%In this paper, we prove that FKM algorithm we a universal cycle for $\mathbf{S}$ if $\mathbf{S}$ is closed under rotation, and the necklaces in $\mathbf{S}$ satisfy an additional closure properties: If a string $a_1  a_2  \cdots  a_{n} \in \mathbf{S}$ is a necklace, then $a_1  a_2  \cdots  a_{n-i}  k^{i}  \in \mathbf{S}$ for all $0 \leq i \leq n$.
In this paper, we prove that the FKM algorithm produces a universal cycle for a set $\mathbf{S}$ if $\mathbf{S}$ is closed under rotation, and the necklaces in $\mathbf{S}$ form a $k$-suffix language. %the necklaces in the set is $k$-suffix language.
%.
%universal cycles for these sets $\mathbf{S}$ can be constructed greedily or by necklace concatenation.
The universal cycle can also be constructed greedily, and is the lexicographically smallest universal cycle for $\mathbf{S}$. 
\end{abstract}
\end{comment}

