%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id: lyndonWords.tex,v 1.1.1.3 2004/10/21 15:52:51 nthiery Exp $
% File:		lib/COMBINAT/DOC/lyndonWords.tex
% Authors:	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
% Purpose:	Documentation for the domain combinat::lyndonWords
% Created:	Wed Jan 28 23:42:48 2004
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{lyndonWords}{Nicolas M. Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{Lyndon words}
  \de{}
\end{MInfo}

\begin{MIntro}
  \eng{\Mthis{} provides functions for counting, generating, and
    manipulating necklaces Lyndon words.}
  \de{}
  \eng{Further functions are documented theme by theme in separate help
    pages:
    \begin{itemize}
    \item Lyndon words with prescribed evaluation
      \Mup{combinat::lyndonWords::fromEvaluation},
    \item Lyndon words with prescribed content:
      \Mup{combinat::lyndonWords::fromContent}.
    \end{itemize}}
\end{MIntro}

\MKeywords{combinatorics, Lyndon words, aperiodic necklaces}

\begin{MDetails}
  \eng{A \emph{Lyndon word} is an aperiodic necklace (see
    \Mup{combinat::necklaces}), that is an aperiodic word, considered
    up to a cyclic rotation. For example, \Mex{[2,1,3,1]},
    \Mex{[1,3,1,2]}, \Mex{[3,1,2,1]}, and \Mex{[1,2,1,3]} all
    represent the same Lyndon word, but \Mex{[1,2,1,2]} is not a
    Lyndon word.}

  \eng{If the letters (or \emph{beads}) of a Lyndon word can be
    ordered then, by convention, its canonical representative is the
    lexicographically smallest element in its equivalence class. In
    the example above, that would be \Mex{[1,2,1,3]}.}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::necklaces}

\begin{MDomEntries}
  \MDomEntry{domtype}
     \eng{The \mupad\ domain to represent Lyndon words: \Mup{DOM_LIST}}
\end{MDomEntries}

\MSuperDomain{Dom::BaseDomain}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}


\begin{MChanges}
  \version{3.1}
  \eng[New domain]{\Mthis{} is a new domain} %
\end{MChanges}

\end{Mhelppage}


\begin{Mhelppage}{lyndonWords::fromEvaluation}{X.~Molinero and N~.Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{Lyndon words with prescribed evaluation}
\end{MInfo}

\begin{MIntro}
  \eng{The combinatorial class of integral Lyndon words with
    prescribed evaluation}
\end{MIntro}

\begin{MDetails}
  \eng{An \emph{integer Lyndon word} is a Lyndon word whose operands
    are positive integers.} %
  
  \eng{The \emph{evaluation} of an integer Lyndon word \Mex{w} is a
    list \Mex{c} such that \Mex{c[i]} is the number of occurrences of
    \Mex{i} in \Mex{w}. For example, the evaluation of
    \Mex{[1,1,1,2,1,4,4]} is \Mex{[4,1,0,2]}. See
    \Mup{combinat::words::evaluation} for details.} %
  
  \eng{Some functions here only deal with evaluations that are
    compositions. In other words the corresponding Lyndon words should
    contain all the integers in a range \Mex{1..k} (counter examples:
    \Mex{[2,2,3]} or \Mex{[1,4,3,3]}).}
\end{MDetails}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a Lyndon word}
  \call{\Mtype{any type} object, \Mopt{\Mtype{composition} evaluation}}
  \eng{Returns whether \Mpar{object} is a Lyndon word.}
  \eng{If the optional argument is present, returns whether
    \Mpar{object} is a Lyndon word with evaluation \Mpar{evaluation}.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of integer Lyndon words with prescribed evaluation}
  \call{\Mtype{integer list} evaluation}
  \eng{Returns the number of integer Lyndon words with evaluation
    \Mex{evaluation}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the integer Lyndon words with prescribed evaluation}
  \call{\Mtype{composition} evaluation}
  \eng{Returns the list of the integer Lyndon words with evaluation
    \Mex{evaluation}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for the integer Lyndon words with prescribed evaluation}
  \call{\Mtype{composition} evaluation}
  \eng{Returns a generator for the integer Lyndon words with evaluation
    \Mex{evaluation}.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-basic}
  \eng{There are $3$ Lyndon words with three 1's and three 2's:}
  \begin{Mexin}
combinat::necklaces::fromEvaluation::list([3, 3])
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 1, 2, 1, 2], [1, 1, 2, 2, 1, 2], [1, 1, 2, 1, 2, 2],

   [1, 1, 1, 2, 2, 2]]
  \end{Mexout}
  \eng{On the other hand, \Mex{[1,1,1]} is periodic, so there are no
    Lyndon word with three 1's:}
  \begin{Mexin}
combinat::lyndonWords::fromEvaluation::list([3])
  \end{Mexin}
  \begin{Mexout}
                              []
  \end{Mexout}
\end{MExample}

\MSuperDomain{Dom::BaseDomain}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\begin{MBackground}
  \eng{The generation algorithm for Lyndon words with prescribed
    evaluation is the same as for necklaces; see
    \Mup{combinat::necklaces} for details.}
\end{MBackground}

\begin{MChanges}
  \version{3.1}
  \eng[New domain]{\Mthis{} is a new domain} %
\end{MChanges}

\end{Mhelppage}

\begin{Mhelppage}{lyndonWords::fromContent}{X.~Molinero and N~.Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]

\begin{MInfo}
  \eng{Lyndon words with prescribed content}
\end{MInfo}

\begin{MIntro}
  \eng{The combinatorial class of Lyndon words with prescribed
    content}
\end{MIntro}

\begin{MDetails}
  \eng{This domain is a wrapper around
    \Mup{combinat::necklaces::fromEvaluation} to make it easy to
    generate necklaces by content; the available methods are the same,
    but take contents instead of evaluations as arguments.} %
  
  \eng{To decide on the canonical representative of a Lyndon word, the
    letters appearing in the content are ordered as in \Mex{sort}.}
\end{MDetails}

\begin{MExample}{ex-fromContent}
  Here are all the Lyndon words containing three \Mex{a}'s, one
  \Mex{b}, and two \Mex{d}'s:
  \begin{Mexin}
combinat::lyndonWords::fromContent([a, a, a, b, d, d])
  \end{Mexin}
  \begin{Mexout}
[[a, b, a, d, a, d], [a, a, d, d, a, b], [a, a, d, b, a, d],

   [a, a, d, a, d, b], [a, a, d, a, b, d], [a, a, b, d, a, d],

   [a, a, b, a, d, d], [a, a, a, d, d, b], [a, a, a, d, b, d],

   [a, a, a, b, d, d]]
  \end{Mexout}
\end{MExample}


\begin{MChanges}
  \version{3.1}
  \eng[New domain]{\Mthis{} is a new domain} %
\end{MChanges}

\end{Mhelppage}
