Circle Formation of Weak Robots and Lyndon Words
Yoann Dieudonn\'e \qquad Franck Petit
LaRIA
CNRS FRE 2733
Universit\'{e} de Picardie Jules Verne
Amiens
France
%\subsection*{\centering Abstract} %\vspace*{-3mm} A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. In this paper, we show how Lyndon words can be used in the distributed control of a set of $n$ weak mobile robots. By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction, and unable to communicate in an other way than observation. An efficient and simple deterministic protocol to form a regular $n$-gon is presented and proven for $n$ prime.
LaRIARR-2006-05.tex
\documentclass[11pt]{article} 
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float}
\usepackage{algorithm}
\usepackage{algorithmic}
\marginparwidth 0pt
\oddsidemargin  0pt
\evensidemargin  0pt
\marginparsep 0pt
\topmargin  -0.6in
\textwidth   6.6in
\textheight  8.7 in

\graphicspath{{figures/}{./}}

\newenvironment{proof}{{\bf Proof. } }{{\hfill $\Box$}\vspace{.5pc}}
\newtheorem{theorem}{Theorem}%[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{property}[theorem]{Property}
\newtheorem{specif}[theorem]{Specification}
\floatstyle{ruled}

%\documentclass{article} %[english]{article}
%\pagestyle{empty}
%\setlength{\textwidth}{7in}
%\setlength{\textheight}{9.125in}
%\setlength{\columnsep}{0.5in}
%\setlength{\topmargin}{-0.8in}
%\setlength{\oddsidemargin}{-0.25in}
%\setlength{\parindent}{5 ex}
%\headsep       42pt   % distance de '3' � '4', la distance entre l'en-t�te et le texte
%
%%\usepackage{float}
%\usepackage{graphicx}
%\usepackage{amssymb}
%\usepackage[english]{./algorithme}
%%\usepackage{/home/dea/yd-laria/algorithme/algorithme}
%%\usepackage{amsmath,amsthm}
%%\usepackage{../algorithme/algorithme}
%\makeatletter
%\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt \abovedisplayskip 11pt
%plus2pt minus5pt\belowdisplayskip \abovedisplayskip \abovedisplayshortskip \z@
%plus3pt\belowdisplayshortskip 6pt plus3pt
%minus3pt\let\@listi\@listI}
%%the following line was changed
%\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}
%\def\section{\@startsection{section}{1}{\z@}{24pt plus 2 pt
%minus 2 pt} {12pt plus 2pt minus 2pt}{\large\bf}}
%\def\subsection{\@startsection {subsection}{2}{\z@}{12pt
%plus 2pt minus 2pt}{12pt plus 2pt minus 2pt}{\subsize\bf}}
%
%
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}
%
%\floatstyle{ruled}
%\newfloat{algorithm}{tbp}{loa}
%\floatname{algorithm}{Algorithm}
%\newtheorem{subproblem}{Subproblem}
%\newtheorem{definition}{Definition}[section]
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}{Lemma}[section]
%\newtheorem{example}{Example}[section]
%\newtheorem{remark}{Remark}[section]
%\newtheorem{proof}{Proof}[section]
%\usepackage{babel}
%\makeatother
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  Entete BOB BEGIN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\fixme}[1]{\fbox{\textsl{{\bf #1}}}}
\newcommand{\FIXME}[1]{\fixme{#1} \marginpar[\null\hspace{2cm}
FIXME]{FIXME}}
\floatstyle{ruled}
\newfloat{algo}{thp}{lop}%[section]
\floatname{algo}{Algorithm}
%\newcolumntype{L}{>{$}l<{$}}
\newcommand{\TRUE}{\mathtt{true}}
\newcommand{\FALSE}{\mathtt{false}}
\newcommand{\R}{\mathtt{R}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\OR}{\mathtt{O}}
%\newcommand{\BEGIN}{\begin{tabular}[t]{@{\hspace{15pt}}l}}
%\newcommand{\END}{\end{tabular}}
\newcommand{\IF}[1]{\textbf{if} {#1}}
\newcommand{\THEN}{\textbf{then} }
\newcommand{\ELSE}{\textbf{else} }
\newcommand{\ELSEIF}{\textbf{elseif} }
\newcommand{\ENDIF}{\textbf{endif} }
\newcommand{\FOR}[3]{\textbf{for } ({#1}; {#2}; {#3}) \textbf{do }}
\newcommand{\FORALL}[1]{\textbf{for all} {#1} \textbf{do }}
\newcommand{\FOREACH}[1]{\textbf{for each} {#1} \textbf{do }}
\newcommand{\WHILE}[1]{\textbf{while} {#1} \textbf{do }}
\newcommand{\REPEAT}{\textbf{repeat} }
\newcommand{\FOREVER}{\textbf{forever} }
\newcommand{\DONE}{ \textbf{done}}


\newcommand{\ALGOHEADER}[3]
{\begin{tabular}[t]{@{\extracolsep{0pt}}p{#3}l}
    \textbf{#1} &
    \begin{tabular}[t]{@{\hspace{15pt}}l}
        #2
    \end{tabular}
 \end{tabular}\smallskip
}

\newcommand{\CONST}[1]      {\ALGOHEADER{Constants: }{#1}{.5in}}
\newcommand{\VAR}[1]        {\ALGOHEADER{Variables: }{#1}{.5in}}
\newcommand{\LOCALVAR}[1]   {\ALGOHEADER{Local  Variables: }{#1}{1.2in}}
\newcommand{\MACRO}[1]      {\ALGOHEADER{Macros: }{#1}{.5in}}

\newcommand{\FUNCTION}[2]   {\textbf{function}  ${#1}$: \textbf{{#2}}}
\newcommand{\RETURN}[1]     {\textbf{return} {#1}}
\newcommand{\PROC}[1]       {\textbf{procedure} ${#1}$}
\newcommand{\INIT}[1]       {\textbf{initially} ${#1}$}
\newcommand{\ACTION}        {\textbf{actions:}}

\newcommand{\MAC}[2]
{
   ${#1} \equiv $
   \begin{tabular}[t]{@{\extracolsep{0pt}}l}
       #2
   \end{tabular}
}

\newcommand{\SEND}[2]{\textbf{send} $#1$ \textbf{to} $#2$}
\newcommand{\RCV}[1]{\textbf{upon} receipt \textbf{of} $#1$}
\newcommand{\RCVF}[2]{\textbf{upon} receipt \textbf{of} $#1$ \textbf{from} $#2$}

\newcommand{\PROCINIT}{\textbf{upon} INITIALIZATION}

\newcommand{\BEGLIST}{\begin{list}{}{\partopsep -3pt \parsep -2pt \listparindent -0pt \labelwidth .5in}}
\newcommand{\ENDLIST}{\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  Entete BOB END   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\begin{document}

\thispagestyle{empty}
\begin{center}
LaRIA~: Laboratoire de Recherche en Informatique d'Amiens\\
Universit� de Picardie Jules Verne -- CNRS FRE 2733\\
33, rue Saint Leu, 80039 Amiens cedex 01, France\\
Tel : (+33)[0]3 22 82 88 77\\
Fax : (+33)[0]03 22 82 54 12\\
\underline{http://www.laria.u-picardie.fr}
\end{center}

\vspace{7cm}

\begin{center}
\parbox[t][5.9cm][t]{10cm}
{\center

{\bf Circle Formation of Weak Robots\\ 
     and\\
     Lyndon Words

\bigskip

Yoann Dieudonn\'e$^{\rm a}$ \qquad Franck Petit$^{\rm a}$
}
\bigskip

\textbf{L}aRIA \textbf{R}ESEARCH \textbf{R}EPORT~: LaRIA-2006-05\\
(May 2006)
}
\end{center}

\vfill

\hrule depth 1pt \relax

\medskip

\noindent
$^a$ LaRIA, Universit� de Picardie Jules Verne, \{Yoann.Dieudonne,Franck.Petit\}@u-picardie.fr

\vspace{-2cm}
\pagebreak

\title{ Circle Formation of Weak Robots and Lyndon Words} 
%\title{ Circle Formation For a Prime Number of Weak Robots} 
%any Prime Number of Anonymous Oblivious Robots  }
\author{Yoann Dieudonn\'e \qquad Franck Petit\\
LaRIA, CNRS FRE 2733\\
Universit\'{e} de Picardie Jules Verne\\
Amiens, France}
%\author{\begin{tabular}[t]{c@{\extracolsep{8em}}c}
%Yoann DIEUDONNE & Franck PETIT \\
%LaRIA, Laboratoire de Recherche & LaRIA, Laboratoire de Recherche\\
%en Informatique d'Amiens & en Informatique d'Amiens\\
%33 rue St Leu, 80000 Amiens, France & 33 rue St Leu, 80000 Amiens, France\\
%yoann.dieudonne@u-picardie.fr & franck.petit@u-picardie.fr 
%\end{tabular}}
\date{}
\maketitle

\begin{abstract}
%\subsection*{\centering Abstract}
%\vspace*{-3mm}
A Lyndon word is a non-empty word strictly smaller in the lexicographic order
than any of its suffixes, except itself and the empty word.  In this paper, we show how Lyndon
words can be used in the distributed control of a set of $n$ weak mobile robots.
By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction,
and unable to communicate in an other way than observation. 
An efficient and simple deterministic protocol to form a regular $n$-gon is presented and proven 
for $n$ prime.  
\end{abstract}

\section{Introduction}
A Lyndon word is a non-empty word strictly smaller in the lexicographic order
than any of its suffixes, except itself and the empty word.  
Lyndon words have been widely studied in the combinatorics of words area~\cite{L83}.  
However, only a few papers consider Lyndon words addressing issues in other 
areas than word algebra, e.g.,~\cite{C04,DR04,SM90}.

In this paper, we address the class of distributed systems where computing units are
\emph{autonomous} \emph{mobile} robots (or agents), i.e., devices equipped 
with sensors which do not depend on a central scheduler and designed to move in a two-dimensional plane. 
Also, we assume that the robots cannot remember any previous observation nor computation performed 
in any previous step.  Such robots are said to be \emph{oblivious} (or \emph{memoryless}). 
The robots are also \emph{uniform} and \emph{anonymous}, i.e, they 
all have the same program using no local parameter (such that an identity) 
allowing to differentiate any of them.
Moreover, none of them share any kind of common coordinate mechanism or common 
sense of direction, and they communicate only by observing the position of the others.

%UN PREMIER JUS QUE JE GARDE POUR L'INSTANT
%In this paper, we show how Lyndon words can be applied in the distributed control 
%of a set of $n$ autonomous mobile robots. 
%By \emph{mobile robots}, we mean units (or agents) equipped with sensors designed 
%to move in a two-dimensional plane.  \emph{Autonomous} means that do not depend 
%on a central scheduler. We assume \emph{uniform anonymous} robots, i.e., they 
%all have the same program using no local parameter (such that an identity) 
%allowing to differentiate any of them.
%Furthermore, they share no kind of common coordinate mechanism, they communicate 
%only by observing the position of the others, and they are \emph{oblivious}
%(or \emph{memoryless}), i.e., they cannot remember any previous observation nor 
%computation performed in any previous step.  

The motivation behind such a weak and unrealistic model is the study of the minimal level of ability 
the robots are required to have in the accomplishment of some basic cooperative tasks in a deterministic 
way~\cite{SS90,SY99,FPSW99,P02}.  
Among them, the \emph{Circle Formation Problem} (CFP) has received a particular attention. %~\cite{D95,SS96,DK02,CMN04,K05}. 
The CFP consists in the design of a protocol insuring that starting from an initial arbitrary configuration, all $n$ robots 
eventually form a circle with equal spacing between any two adjacent robots.  In other words, a \emph{regular n-gon} must be formed 
when the protocol terminated.  

An informal CFP algorithm is presented in~\cite{D95} to show 
the relationship between the class of pattern formation algorithms and the concept of self-stabilization
in distributed systems~\cite{D00}.  
In~\cite{SS96}, an algorithm based on heuristics is proposed for the formation of a cycle approximation.
A CFP protocol is given in~\cite{SY99} for non-oblivious robots with an unbounded memory.  
Two deterministic algorithms are provided in~\cite{DK02,CMN04}.  In the former work, the robots
asymptotically converge toward a configuration in which they are uniformly distributed on the boundary 
of a circle.  This solution is based on an elegant Voronoi Diagram construction.  
The latter work avoid this construction by making an extra assumption on the initial position of robots.  
All the above solutions work in a semi-asynchronous model.  The solution in~\cite{K05} works on a fully asynchronous model, but 
when $n$ is even, the robots may only achieve a biangular circle---the distance between two adjacent robots is alternatively
either $\alpha$ or $\beta$.  

In this paper, we show a straight application of the properties of Lyndon words.  They are used 
to build and to prove an efficient and simple deterministic protocol solving the CFP 
for a prime number of robots.% greater than or equal to $5$.  
%A simple deterministic is also provided for a prime number of robots lower than $5$, which
%solves the CFP for any prime number of robots. 

%Under this Coordinated control of multi-agent/multi-vehicle systems in a distributed fashion 
%has attracted several researchers with rather diverse backgrounds in control theory, 
%biology, physics, engineering and artificial intelligence. One of the main 
%reason for this interest, is that a such system is often preferable to only 
%one complex unit for many reasons: ability to solve tasks otherwise unsolvable by a 
%single robot; advantages that can arise from a distributed and parallel solution to the 
%given problems, such as a faster computation; for fault tolerance considerations; 
%the decreased cost due to the use of simpler and cheaper individual robots. 
%In this areas, most studies on robot control problems resulted in the designed 
%of algorithms based on heuristics, with little emphasis on formal analysis of 
%the correctness, termination or complexity properties of the algorithm. 
%
%During the last decade, various aspects of these problems have been studied from the point of view of distributed computing, where the focus is to identify the minimal capabilities a cohort of distributed robots must have in order to accomplish certain basic tasks. Consequently, the models adopted in the studies assume the robots to be relatively weak and simple. In particular, each robot is modeled as a point allowed to move on a two dimensional plane, and it is equipped with sensors (with unlimited visibility) that let it observe the positions of the other robots in the plane. 
%Moreover, the robots are anonymous (no identity), oblivious (no memory of past actions), no common sense of distance and direction. They cannot communicate explicitly with each other : communication is based only on the position of the others.
%Based on this model, a basic task that has received considerable attention is the {\it circle formation problem}, defined as follows. Given an initial configuration of $n$ autonomous mobile robots, all $n$ robots should form a circle with equal spacing between any two adjacent robots (i.e. a regular $n$-gon). Recently Katreniak solves this problem with an odd number of robots\footnote{However the general solution of the circle formation problem remains an open problem}. 
%
%In this paper, we propose to prove again this result with any prime number of robots, by providing an original   algorithm based on the {\it Lyndon Words} which are, by definition, words both primitive and minimal. Lyndon Words have neat properties led to elaborate subtle solutions within combinatorics on words. In spite of their wealth, apart from combinatorics on words, their applications are non-existent except in music.   

%The main idea here is to let each robot execute a simple algorithm and plan its motion adaptively based on the observed movement of other robots, so that the robots as a group will manage to form a circle. Besides, seeing that it does not require robots to memorize past actions, our algorithm is self-stabilizing\footnote{Self-stabilization is the property of a system which, started in an arbitrary state, always converges toward a desired behavior \cite{D00}}, provided that, initially, no two robots are located in the same position\footnote{if two robots with the same coordinate system happen to have the same initial position, it would be impossible to separate them in a deterministic manner. }.  

%	Based on this model, we study the problem of the robots positioning themselves to form a circle\footnote{we do not prescribe the position of the circle in the world, and we do not prescribe the size of the circle, just because the robots do not have a notion of the world coordinate system's origin or unit of length} with equal spacing between any two adjacent robots ( i.e a regular n-gon). 
	
%	The main contribution of this paper is to propose a deterministic distributed algorithm by which a group of \emph{n} (\emph{n} prime) oblivious mobile robots eventually form a uniform circle (\emph{n}-gon). Because of the particular nature of the prime numbers, forming a regular $n$-gon is relatively simple. Besides, seeing that it does not require robots to memorize past actions, our algorithm is self-stabilizing\footnote{Self-stabilization is the property of a system which, started in an arbitrary state, always converges toward a desired behavior \cite{Dolev}}, provided that, initially, no two robots are located in the same position\footnote{if two robots with the same coordinate system happen to have the same initial position, it would be impossible to separate them in a deterministic manner. }.  
%	The main idea here is to let each robot execute a simple algorithm and plan its motion adaptively based on the observed movement of other robots, so that the robots as a group will manage to form a circle.
%\subsection{Related Work}
	
	 
\section{Preliminaries}

In this section, we define the distributed system and the problem considered in this paper. 
Next, the Lyndon words are introduced. 

\paragraph{Distributed Model.}

We adopt the model of \cite{SY96}.  
The \emph{distributed system} considered in this paper consists of $n$ robots  
$r_{1}, r_{2},\cdots , r_{n}$, where $n$ is prime---the subscripts $1,\ldots ,n$ are used for notational purpose only.
Each robot $r_{i}$, viewed as a point in the Euclidean plane, move on this two-dimensional 
space unbounded and devoid of any landmark.  When no ambiguity arises, $r_{i}$ also denotes the point in the plane occupied by that robot. 
It is assumed that the robots never collide and that two or more robots may simultaneously occupy the same physical location. 
Any robot can observe, compute and move with infinite decimal precision.
The robots are equipped with sensors allowing to detect the instantaneous position of the other robots in the plane.  
Each robot has its own local coordinate system and unit measure.  
The robots do not agree on the orientation of the axes of their local coordinate system, nor on the unit measure. 
They are \emph{uniform} and \emph{anonymous}, i.e, they all have the same program using no local parameter (such that an identity) 
allowing to differentiate any of them.  %They share no kind of common coordinate mechanism nor common sense of direction (e.g., compass).
They communicate only by observing the position of the others and they are \emph{oblivious}, i.e.,
none of them can remember any previous observation nor computation performed 
in any previous step. \\

Time is represented as an infinite sequence of time instant $t_0, t_1, \ldots, t_j, \ldots$ 
The set of positions in the plane occupied by the $n$ robots at a given time instant  
$t_j$ ($j\geq0$) is called a \emph{configuration} of the distributed system.   
At each time instant $t_j$ ($j\geq 0$), each robot $r_i$ is either {\it active} or {\it inactive}. 
The former means that, during the computation step $(t_j,t_{j+1})$, using 
a given algorithm, $r_i$ computes in its local coordinate system a position $p_i(t_{j+1})$ depending 
only on the system configuration at $t_j$, and moves towards $p_i(t_{j+1})$---$p_i(t_{j+1})$ can be equal to
$p_i(t_j)$, making the location of $r_i$ unchanged.
In the latter case, $r_i$ does not perform any local computation and remains at the same position. 

The concurrent activation of robots is modeled by 
the interleaving model in which the robot activations are driven by a \emph{fair scheduler}.  
At each instant $t_j$ ($j\geq 0$), the scheduler 
arbitrarily activates a (non empty) set of robots.  
Fairness means that every robot is infinitely often activated by the scheduler.  

\paragraph{The Circle Formation Problem.}
\label{circle}
Consider a configuration at time $t_k$ ($k\geq 0$) in which the positions of the $n$ 
robots are located at distinct positions on the circumference of a 
non degenerate circle $C$---the radius of $C$ is greater than $zero$.
At time $t_k$, the \emph{successor} $r_j$ of any robot $r_i$, $i,j \in 1 \ldots n$ and $i \neq j$, is 
the unique robot such that no robot exists between $r_i$ and $r_j$ on $C$ in the
clockwise direction.  Given $r_i$ and its successor $r_j$ on $C$ centered in $O$,  
$\widehat{r_i O r_j}$ denotes the angle between $r_i$ and $r_j$, i.e., the angle centered in $O$ and 
with sides the half-lines $[O,r_i)$ and $[O,r_j)$.  \\

The problem considered in this paper consists in the design of a 
distributed protocol which arranges a group of $n$ ($n \geq 2$) 
mobile robots with initial distinct positions  
into a \emph{non degenerate regular $n$-gon} 
in finite time
, i.e., the robots eventually 
take place in a non degenerate circle $C$ centered in $O$
such that for every pair $r_i,r_j$ of robots, if $r_j$ is the successor of $r_i$ on $C$,
then $\widehat{r_i O r_j} = \alpha$, where $\alpha= \frac{2\pi}{n}$.  
Angle~$\alpha$ is called the \emph{characteristic angle} of the $n$-gon.

%\begin{specif}[CFP]
% The circle formation a group of $n$ robots $r_{1}, r_{2}, r_{3}, \cdots, r_{n} $ with distinct positions
% and located arbitrarily on the plane, eventually, in finite time, arrange them at regular intervals 
% on the boundary of a non degenerate circle. We say robots form a circle or a regular 
% \emph{n}-gon(see fig \ref{Ngon}). 
%\end{specif}
%\begin{figure}[H]
% \centering
%\includegraphics*[width=8cm]{./uniform.eps}
%\caption{Circle Formation Problem}
%\label{CircleProblem}
%\end{figure}
%
% \begin{figure}[H]
%\centering
%\includegraphics*[width=8cm]{./ngon.eps}
%\caption{The robots form a circle or a regular $n$-gon. $\alpha=\frac{360^{\circ}}{n}$ is the characteristic angle of the $n$-gon}
%\label{Ngon}
%\end{figure}
%Another simplest problem (see fig \ref{simplest}) consists in arranging the robot to eventually be located arbitrarily 
%on the circumference of a non degenerate circle, in finite time.  
%
% \begin{figure}[H]
% \centering
%\includegraphics*[width=8cm]{./circle.eps}
%\caption{Simplest problem}
%\label{simplest}
%\end{figure}
%
%In \cite{DK02}, Defago et. al propose an algorithm that asymptotically converges toward a situation wherein robots 
%form a regular \emph{n}-gon. However, they describe an original deterministic solution, 
%called $\phi_{circle}$, based on Voronoi Diagram, and prove its correctness (\emph{Theorem 2}, 
%\cite{DK02}) for the simplest problem. 

%\subsection{Lyndon Word, String of Angles}
%
% \subsubsection{Basic Definitions on Strings} 
% 
%A {\it string} $s$ is a tuple $<s_{0},\cdots,s_{n-1}>$ where $s_{i}$ are called the {\it characters} or {\it letters} of $s$; the i-\emph{th} character in $s$ will be denoted by $s[i]$. We denote by $\epsilon$ the empty string.
%
%For our purposes, we assume that the characters of a string are real numbers. Given a string $s$, its {\it length} is denoted by $|s|$, and $s[i \cdots j]=<s[i],\cdots,s[j]>$, with $i \leq j$ indicates any {\it substring} of $s$. Given two strings $s$ and $s'$, we denote the {\it concatenation} of $s$ and $s'$ by $s \circ s' = <s_{0},\cdots,s_{n-1},s'_{0},\cdots,s'_{n-1},>$. When no ambiguity arises, we denote $s \circ s'$ by $ss'$. Given two strings $s$ and $s'$, with $|s|=|s'|$, we say they are {\it lexicographically equal}, denoted by $s=_{lex}s'$ (or shortly $s=s'$ by misuse of language), if $s[i]=s'[i]$, for all $ 0\leq i \leq n-1$. We say $s$ is {\it lexicographically smaller} than $s'$, denoted by $s \leq_{lex} s'$, if there exists an index $j$, $ 0\leq j \leq n-1$, such that for all $ i < j$, $s[i]=s'[i]$, and $s[j] < s'[j]$. Finally, the minimum between them is defined as follows:
%$$ min(s,s') =
%\left\{
%\begin{array}{l}
%s \mbox{ if } s<_{lex}s' \mbox{ or } s=s'\\ 
%s' \mbox{ otherwise } 
%\end{array}
%\right .
%$$ 
%Let $s$ be a string and $k$ an integer, $s$ any string, the  {\it $k^{th}$ power} of $s$ is the string denoted by $s^{k}$ such that $s^{0}=\epsilon$, and $s^{k}=s^{k-1} s$.
%Given a string $s$, if there exists a string $p$ such that $s=p^{k}$ with $k \geq 2$, then $s$ is not {\it primitive}. Otherwise, we say that $s$ is primitive.
%Given a string $s= s[0,\cdots,n-1]$, the $j^{th}$ {\it rotation} of $s$ is defined to be the string 
%$$ R_{j}(s)= s[j,\cdots,n-1]s[0,\cdots,j-1] \mbox{ with }j \in 0,\cdots,n-1$$ We remark $R_{0}(s)=s$. A string $s$ is said to be {\it minimal} if $s \leq_{lex} R_{j}(s)$ for every integer $j \in 0,\cdots,n-1$
%
% 
%\subsubsection{Lyndon Word}
% %Lyndon Words have been intensively studied in combinatorics on words but its applications are non-existent except . 
%A {\it Lyndon Word} is a string which is both primitive and minimal. In literature, we can meet the following basic lemma about Lyndon Words 
%\begin{lemma}
%\label{lemmaMot}
%A nonempty string $s$ is said to be a Lyndon Word if and only if $s <_{lex} R_{j}(s)$ for every integer $j \in 1,\cdots,|s|-1$
%\end{lemma}
% Thus, for example, every single letter must be a Lyndon Word. Further, we see that while $ab$ is a Lyndon Word, $ba$ is not; similarly, $aab$ is a Lyndon Word, but neither $aba$ nor $baa$. 
%
% \subsubsection{String of Angles}
% The notion of string of angles was first introduced in \cite{CP02}, by Cieliebak and Prencipe in order to solve the Gathering Problem\footnote{this problem consists to make the robots gather at one point in a finite time}. In this paper, we reuse this notion for our problem.
% 
% 
%  Given $n$ robots $r_{1},r_{2},\cdots,r_{n}$ located arbitrarily on the boundary of a non degenerate circle $C$. For an arbitrary robot $r_{k}$, $1 \leq k \leq n$, the string of angles $SA(r_{k})$ is defined by the following algorithm :  
% 
%
%
%\begin{algorithme}
%\Function{ComputeSA}
%    {$r_{k}$: \textbf{robot}}{string}
%{
%    r:= r$_{k}$\\
%    \For{(i=0 ; i $\leq$ n-1; i:=i+1)}
%    {r':= Succ(r);\\ SA[i]:= $Angle(r,r')$;\\ r:=r';}
%    
%    \Return SA;
%}
%\caption{ComputeSA}
%\end{algorithme}
%
%
%
%Here, the successor of $r$, computed by $Succ(r)$ is the robot adjacent\footnote{ two robots are said adjacent if there exist no robot between them on $C$} to $r$, on $C$, in {\bf clockwise}. The routine $Angle(r,r')$ returns the angle between $r$ and $r'$, centered in the center of $C$ . Note that the robots do not have a common coordinate system. However, each robot can locally distinguish between a clockwise and counterclockwise orientation. Given $r_{k}$, procedure $Succ()$ defines unique successors, and thus $ComputeSA(r_{k})$ defines a unique string of angles. Given two starting robots $r_{i}$ and $r_{j}$, then $SA(r_{i})$ is a rotation of $SA(r_{j})$.
% \begin{figure}[H]
% \centering
%\includegraphics*[width=8cm]{./string.eps}
%\caption{String of Angles}
%\end{figure}
%For an arbitrary robot $r_{k}$, $1 \leq k \leq n$, the {\it  reverse string of angles} $revSA(r_{k})$ is defined in the same way, apart from $Succ(r)$ : in this case the routine returns the successor of $r$ in {\bf counterclockwise}. Note if the configuration is a regular $n$-gon, then for all robot $r$, $SA(r)=revSA(r)=\alpha^{n}$ with $\alpha=\frac{360^{\circ}}{n}$ which is the characteristic angle of the $n$-gon. 
%
%Let {\it $SetLyndonWord$} be the set of all the robots $r$ such that $SA(r)$ or $revSA(r)$ is a Lyndon word.  

\paragraph{Lyndon Word.}

Let an ordered alphabet $A$ be a finite set of letters.  Denote $\prec$ an order on $A$. 
A non empty \emph{word} $w$ over $A$ is 
a finite sequence of letters $a_1,\ldots,a_i,\ldots,a_l$, $l>0$.  
The \emph{concatenation} of two words $u$ and $v$, denoted $u\circ v$ or simply $uv$, is equal to the word
$a_1,\ldots,a_i,\ldots, a_k,b_1, \ldots, b_j,\ldots,b_l$ such that $u=a_1,\ldots,a_i,\ldots, a_k$ and 
$v=b_1, \ldots, b_j,\ldots,b_l$.  
Let $\epsilon$ be the \emph{empty word} such that for every word $w$, $w\epsilon = \epsilon w = w$.  
The \emph{length} of a word $w$, denoted by $|w|$, is equal to the number of letters of $w$---$|\epsilon|=0$.  

A word $u$ is \emph{lexicographically} smaller than or equal to a word $v$, 
denoted $u \preceq v$, iff there exists either a word $w$ such that $v=uw$ or 
three words $r,s,t$ and two letters $a,b$ 
such that $u=ras$, $v=rbt$, and $a\prec b$.
%
% A priori, pas besoin de ce qui suit
%Finally, the minimum between them is defined as follows:
%$$ min(s,s') =
%\left\{
%\begin{array}{l}
%s \mbox{ if } s<_{lex}s' \mbox{ or } s=s'\\ 
%s' \mbox{ otherwise } 
%\end{array}
%\right .
%$$ 

Let $k$ and $j$ be two positive integers.  The {\it $k^{th}$ power} of a word $w$ is 
the word denoted $s^k$ such that $s^0 = \epsilon$, and $s^k = s^{k-1} s$.
A word $u$ is said to be \emph{primitive} if and only if $u = v^k \Rightarrow k=1$. 
The \emph{$j^{th}$ rotation} of a word $w$, notation $R_j (w)$, is defined by:

$$ 
R_j (w) \stackrel{\mathrm{def}}{=}
\left\{
  \begin{array}{ll}
     \epsilon & \mbox{if } w = \epsilon \\
     a_j,\ldots, a_l,a_1,\ldots,a_{j-1} & \mbox{otherwise } ( w = a_1,\ldots,a_l,\ l\geq 1 )
  \end{array}
\right.
$$
    
Note that $R_1 (w) = w$. A word $w$ is said to be {\it minimal} iff $\forall j \in 1,\ldots, l$,
$w \preceq R_j (w)$.
%
%Let $s$ be a string and $k$ an integer, $s$ any string, the  {\it $k^{th}$ power} of $s$ is the string denoted by $s^{k}$ such that $s^{0}=\epsilon$, and $s^{k}=s^{k-1} s$.
%Given a string $s$, if there exists a string $p$ such that $s=p^{k}$ with $k \geq 2$, then $s$ is not {\it primitive}. Otherwise, we say that $s$ is primitive.
%Given a string $s= s[0,\cdots,n-1]$, the $j^{th}$ {\it rotation} of $s$ is defined to be the string 
%$$ R_{j}(s)= s[j,\cdots,n-1]s[0,\cdots,j-1] \mbox{ with }j \in 0,\cdots,n-1$$ We remark $R_{0}(s)=s$. A string $s$ is said to be {\it minimal} if $s \leq_{lex} R_{j}(s)$ for every integer $j \in 0,\cdots,n-1$

%\subsubsection{Lyndon Word}
 %Lyndon Words have been intensively studied in combinatorics on words but its applications are non-existent except . 
\begin{definition}[Lyndon Word]
\label{def:LW}
A word $w$ ($|w|>0$) is a Lyndon word iff $w$ is nonempty, primitive and minimal, i.e.,
$w \neq \epsilon$ and $\forall j \in 2,\ldots, |w|,\ w \prec  R_{j}(w)$.
\end{definition}
%In literature, we can meet the following basic lemma about Lyndon Words 
For instance, if $A=\{a,b\}$, then $a$, $b$, $ab$, $aab$, $abb$ are Lyndon words, whereas $aba$, and $abab$ are not---
$aba$ is not minimal ($aab \preceq aba$) and $abab$ is not primitive ($abab = (ab)^2$). 


%*************************************************
\section{Algorithm}

In this section, we present our main result based on Lyndon words 
for $n$ robots, $n$ being prime and greater than or equal to $5$.  
Note that if the system contains two robots only, then CFP is trivially 
solved because they always form a $2$-gon.  
If $n=3$, then the three robots always form a triangle, which must be equilateral to
form a regular $3$-gon.  If the triangle is not equilateral, then either
($1$) the three robots belongs to the same line, ($2$) they form an isosceles triangle, or 
($3$) they form an ordinary triangle.  In all cases, it is always possible to elect a unique
robot as the leader which moves to the unique position making the triangle equilateral---%. 
%
%The case where $n=3$ is
%also trivially solved without using Lyndon words---
a formal algorithm for $n=3$ is given and proved in the appendix.  
%So, in this section, we assume that $n$ is prime and greater than or equal to $5$. 

The technique developed in this paper is based on a Leader Election using properties of Lyndon words.  
The words we consider are made over the alphabet such that the letters are the angles between 
neighboring robots located on the boundary of a unique non degenerate circle. 
So, we focus only on configurations where the robots are either all or all but one on the boundary
of the circle.  
Thus, we integrate the first algorithm proposed in \cite{DK02} in our solution, in the sequel refered to 
Algorithm~$\phi_{circle}$.  

\begin{theorem}[\cite{DK02}]
\label{th:DK}
Starting from an arbitrary configuration where $n$ robots are located at distinct positions, 
Algorithm~$\phi_{circle}$ leads the robots into a configuration where the robots are located on 
the boundary of a non degenerate circle.  
\end{theorem}
%We assume the existence of an algorithm, in the sequel referred as Algorithm~$\phi_{circle}$,
%such that starting from an arbitrary configuration where $n$ robots are located at distinct positions, 
%Algorithm~$\phi_{circle}$ leads in finite time the robots into a configuration 
%where the robots are located at distinct positions on the boundary of a non degenerate circle.  
%Such algorithms are provided in \cite{DK02,CMN04,K05}.

In the rest of this section, 
we first present how Lyndon words are used to make a leader election
among $n$ robots located on the boundary of a unique circle.  
Next, we define a particular type of configurations called \emph{oriented} configurations.  
We then give an algorithm to arrange the robots in a regular $n$-gon starting
from an oriented configuration.  
Finally, we provide our general scheme to solve the Circle Formation Problem.  


\subsection{Leader Election}
\label{sub:LE}

%Let us first consider the circle $C$ in the clockwise direction.  
In this subsection,
we use the subscript $i$ in the notation of a robot $r_i$, $i \in 1\ldots n$, to denote the order of the robots in an
arbitrary clockwise direction on $C$.  We proceed as follows:
A robot is arbitrarily chosen as $r_1$ on $C$.
Next, for any $i \in 1\ldots n-1$, $r_{i+1}$ denotes the successor of $r_i$ on $C$ (in the
clockwise direction).  Finally, the successor of $r_n$ is $r_1$. 

Let the alphabet $A$ be the set of $k$ ($k\leq n$) strictly positive reals 
$x_1,x_2,\ldots, x_k$ such that 
$\forall i \in 1\ldots n$, there exists $j \in 1\ldots k$
such that $x_j=\widehat{r_i O r_{i+1}}$, where $O$ is the center of $C$.
An example of such an alphabet is shown in Figure~\ref{fig:SA}---$A= \{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8\}$.

The order on $A$ is the natural order ($<$) on the reals.  So, the lexicographic order $\preceq$
on the words made over $A$ is defined as follows:
$$
u\preceq v \stackrel{\mathrm{def}}{\equiv} 
\left( \exists w |\ v=uw \right) \vee
\left( \exists r,s,t,\ \exists a,b \in A |\ (u=ras) \wedge (v=rbt) \wedge (a<b) \right)
$$
For instance, if $A = \{\frac{\pi}{3}, \frac{\pi}{2}\}$, then 
$
  (\frac{\pi}{3}) \preceq (\frac{\pi}{3} \frac{\pi}{3}) \preceq 
  (\frac{\pi}{3} \frac{\pi}{2}) \preceq  (\frac{\pi}{3} \frac{\pi}{2} \frac{\pi}{2})
  \preceq (\frac{\pi}{2})$.%---each 
%word is shown in brackets to ease the reading.

For each robots $r_i$, let us define the word $SA(r_i)$ (respectively, $\overline{SA(r_i)}$) 
over $A$ ($SA$ stands for ``string of angles''~\cite{CP02}) as follows:
$$
\begin{array}{c}
  SA(r_i)=x_i x_{i+1} \ldots x_n x_1 \ldots x_{i-1}\\
  \mbox{(resp. } \overline{SA(r_i)}=x_{i-1} \ldots x_1 x_n x_{n-1} \ldots x_i \mbox{)}
\end{array}
$$

\begin{figure}[!htbp]
\begin{center}
    \epsfig{file=alphabet.eps, width=0.25\linewidth}
\end{center}
\caption{$SA(r_i)= x_1  (x_2)^2 x_3  x_1  x_4  x_5  x_6  x_7  x_1  x_8$.}
\label{fig:SA}
\end{figure}

An example showing a string of angle is given in Figure~\ref{fig:SA}.
Note that for every robot $r_i$, $|SA(r_i)| = |\overline{SA(r_i)}| = n$.  Moreover, if the configuration is a regular $n$-gon, then 
for every robot $r_i$, $SA(r_i)= \overline{SA(r_i)} = \alpha^{n}$, 
where $\alpha=\frac{2\pi}{n}$ is the characteristic angle of the $n$-gon.


\begin{lemma}
\label{lem:LWS}
If all the robots are at distinct positions on the boundary of a same circle $C$ without forming 
a regular $n$-gon, then there exists exactly one robot $r_i$ such that $SA(r_i)$ is a Lyndon Word.
\end{lemma}
\begin{proof}
We prove this in two steps.  First, we show that $r_i$ always exists.  Next, we show the uniqueness of $r_i$.
\\

\noindent \emph{Existence}.  Let $minSA$ be the string of angle such that 
$\forall i \in 1\ldots n,\ minSA \preceq SA(r_i)$.  Let us show that $minSA$ is a Lyndon word.  
By definition, $minSA$ is minimal.
Assume by contradiction that $minSA$ is not primitive. 
So, by definition, there exists a word $u$ such as $minSA=u^k$ with $k>1$.  
By definition of the $k^{\mbox{th}}$ power of a word $u$, $|minSA|=k*|u|$, $|u|$ 
being a divisor of $n$.  Since $|minSA|=n$ and $n$ is prime, there are only two cases to consider:
\begin{enumerate}
\item $|u| = |minSA|$.  Since $|minSA|=k*|u|$, this implies that $k=1$, which contradicts $k>1$.
\item $|u| = 1$.  In this case, $u$ is a letter ($\in A$), and $minSA=u^n$.  Since the letters 
are angles, the angle between every pair of successive robots is 
equal to the value $u$.  So, the robots form a regular $n$-gon and $u = \alpha$, the characteristic angle 
of the $n$-gon.  This contradicts that the configuration is not a regular $n$-gon.
\end{enumerate}
%Thus, $minSA$ is a word which is both primitive and minimal.  Thus, by definition, $minSA$ is a Lyndon Word. 
%Hence, there exists at least one robot $r_i$ such that $SA(r_i)$ is a Lyndon Word, i.e., the robot $r_i$ 
%such that $SA(r_i)=minSA$. 

\noindent \emph{Unicity}.  Assume by contradiction that there exists two different robots 
$r_i,r_j$ ($r_i\neq r_j$) such that $SA(r_i)$ and $SA(r_j)$ are Lyndon words.  
Since $SA(r_j)$ (respectively, $SA(r_j)$) is a Lyndon word, by Definition~\ref{def:LW},
$\forall k \in 2\ldots n,\ SA(r_i) \prec R_k(SA(r_i))$ 
(resp. $\forall k' \in 2\ldots n,\ SA(r_j) \prec R_k(SA(r_j))$).  
Since $r_i \neq r_j$, there exists $k \in 2\ldots n$ such that $SA(r_j) = R_k(SA(r_i))$ (resp. 
there exists $k' \in 2\ldots n$ such that $SA(r_i) = R_{k'}(SA(r_j))$).
Hence, $SA(r_i) \prec SA(r_j)$ and $SA(r_j) \prec SA(r_i)$.  A contradiction.
%\ENDLIST
\end{proof}

Clearly, following the reasoning as for Lemma~\ref{lem:LWS}:
\begin{lemma}
\label{lem:LWSb}
If all the robots are at distinct positions on the boundary of a same circle $C$ without forming a 
regular $n$-gon, then there exists exactly one robot $r_i$ such that $\overline{SA(r_i)}$ is a Lyndon Word.
\end{lemma}

%Let $WS_{r_i}$ be the set of strings of angles computed in both directions of $C$ by every $r_i$, i.e.,
%$WS= \{SA(r_j),\ \forall j \in 1\ldots n \} \cup \{\overline{SA(r_j)},\ \forall j \in 1 \ldots n \}$.
Let $LWS$ be the set of robots $r_i$ such that $SA(r_i)$ or $\overline{SA(r_i)}$ is a Lyndon word.  

\begin{lemma}
\label{lem:LWS2}
If all the robots are at distinct positions on the boundary of a same circle $C$ without forming a 
regular $n$-gon, then $|LWS| = 2$.
\end{lemma}
\begin{proof}
 From Lemmas~\ref{lem:LWS} and~\ref{lem:LWSb}, %considering its own clockwise direction of $C$, every robot $r_i$ finds 
there exists exactly one robot $r_a$ such that $SA(r_a)$ is a Lyndon word, and 
exactly one robot $r_b$ such that $\overline{SA(r_b)}$ is a Lyndon word.  
However, $r_a$ can be the same robot as $r_b$.  So, $1\leq |LWS| \leq 2$.

Let assume that $|LWS|=1$, i.e., there exists a unique robot $r$ such that both 
$SA(r)=a_1 a_2 \ldots a_n$ and $\overline{SA(r)}=a_n a_{n-1} \ldots a_1$ are Lyndon words. 
Since the robots do not form a regular $n$-gon, $SA(r) \neq a_1^n$.  So, $SA(r)$ contains at least
two different letters.  There are three cases to consider:
\begin{enumerate}
\item $a_n \prec a_1$.  So, $a_n a_1 a_2 \ldots a_{n-1} \prec a_1  \ldots  a_{n-1} a_n$, i.e., 
$R_n(SA(r)) \prec SA(r)$.  This contradicts that $SA(r)$ is a Lyndon word---by 
Definition~\ref{def:LW}, $SA(r) \prec R_n(SA(r))$.  
\item $a_1 \prec a_n$.  So, $a_1 a_n a_{n-1} \ldots a_2 \prec a_n  a_{n-1}  \ldots  a_2 a_1$, i.e., 
$R_n(\overline{SA(r)}) \prec \overline{SA(r)}$.  This contradicts that $\overline{SA(r)}$ is 
a Lyndon word---by Definition~\ref{def:LW}, $\overline{SA(r)} \prec \overline{R_n(SA(r))}$.  
\item $a_1 = a_n$.  Since $SA(r)$ is a Lyndon word, by Definition~\ref{def:LW}, we have 
$a_1 a_2  \ldots a_{n-1} a_n \prec a_n  a_1  a_2  \ldots  a_{n-1}$. %, i.e., 
%$SA(r) \prec R_n(SA(r))$.  
Since $a_1 = a_n$, we have $a_2  \ldots a_{n-1} a_n \prec a_1  a_2  \ldots  a_{n-1}$.
Since $a_1 = a_n$ again, we have also 
$a_2  \ldots a_{n-1} a_n a_1 \prec a_1  a_2  \ldots  a_{n-1} a_n$, i.e., 
$R_2(SA(r)) \prec SA(r)$.  
This contradicts Definition~\ref{def:LW}, $SA(r) \prec R_2(SA(r))$.  
\end{enumerate}
\end{proof}

Now, consider the distributed computation of string of angles.  
We borrow Algorithm~\ref{algo:SA} from \cite{CP02} which describes a function called Function~$ComputeSA$.  
Each robot $r_i$ arbitrarily determines its own clockwise direction 
of $C$ in its local coordinate system.  Note that since the robots are 
uniform, all of them apply the same algorithm to determine the clockwise direction.  However, the robots do not
share a common coordinate system.  So, for any pair $r_i,r_j$, the clockwise direction of $r_i$ (resp., $r_j$) 
may be the counterclockwise of $r_j$ (resp., $r_i$).  

\begin{algo}[htb]
%\begin{footnotesize}
\begin{small}
\begin{tabbing}
  xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= \kill 
\FUNCTION{ComputeSA(r_j)}{word}\\
%\{\\
\>  $SA:=\epsilon$;\ $r:=r_j$;\\
\>  \FOR {$k=1$}{$k\leq n$}{$k:=k+1$}\\
\>  \> $r':= Succ(r)$; %\\
%\>  \> 
$SA := SA \circ Angle(r,r')$; %\\ 
%\>  \> 
$r:=r'$;\\
\>  \DONE\\
\>  \RETURN{$SA$};%\\
%\}
\end{tabbing}
\end{small}
%\end{footnotesize}
\caption{Function $ComputeSA$ for any robot $r_i$}
\label{algo:SA}
\end{algo}

%\begin{figure}[H]
% \centering
%\includegraphics*[width=8cm]{./string.eps}
%\caption{String of Angles}
%\end{figure}

Algorithm~\ref{algo:SA} uses two functions, $Succ(r)$ and $Angle(r,r')$.  The former returns the successor of $r$
in the local coordinate system of the robot executing $Succ(r)$.
The latter returns the absolute value of $\widehat{rOr'}$, where $O$ is the center of $C$.  Using this algorithm,
each robot $r_i$ computes $SA(r_j)$, $\forall j \in 1\ldots n$.  %In the sequel, let us denote
%$\overline{SA(r_i)}$ the reverse word of $SA(r_i)$.  
Similarly, for each robot $r_j$, $\overline{SA(r_j)}$ can also be easily computed by any $r_i$ by either 
computing the mirroring word of $SA(r_j)$ or following 
Algorithm~\ref{algo:SA} and replacing Function~$Succ(r)$ by a function $Pred(r)$, which 
returns the unique predecessor of $r$ in the counterclockwise direction.\\ 

\begin{figure}[!htbp]
\begin{center}
    \epsfig{file=LE.eps, width=0.25\linewidth}
\end{center}
\caption{An example showing how the leader robot $r_L$ is computed ($n=11$).}
\label{fig:LE}
\end{figure}

Let us now describe how the above results can be used to elect a leader.  
An example showing our method is given in Figure~\ref{fig:LE} with $n=11$. 
Following Lemmas~\ref{lem:LWS}, \ref{lem:LWSb}, and \ref{lem:LWS2}, 
when any robot computes the set $LWS$, then $LWS = \{r_a,r_b\}$ and $r_a$ and $r_b$ refer to
the same robots for every robot. 
Consider both half-lines $[O,r_a)$ and $[O,r_b)$.
These two half-lines divide the circle $C$ into two sides,
$C1$ and $C2$, where $n_{C1}$ (resp. $n_{C2}$) represent the number of robots inside $C1$ (resp $C2$).
Note that $n_{C1} + n_{C2} = n-2$.  Since $n-2$ is odd ($n$ is prime), there exists one side with an
even number of robots, and one side with an odd number of robots.  Without lost of generality,
let us assume that $n_{C1}$ is odd.  Let $r_L$ be the unique robot which is the median robot on $C_{1}$,
i.e., the $(\lfloor \frac{n_{C1}}{2} \rfloor +1)^{\mbox{th}}$ robot starting indifferently from $r_a$ or $r_b$.

Let us define Function $Elect()$ which returns the unique leader robot $r_L$ for every robot $r_i$.
%\end{itemize}
\begin{lemma}
\label{lem:LE}
If all the robots are at distinct positions on the boundary of a same circle $C$ without forming a 
regular $n$-gon, then for every robot $r_i$, Function~$Elect()$ returns a unique leader robot $r_L$ 
among the $n$ robots.  
\end{lemma}


\subsection{Oriented Configuration}
\label{sub:OC}

%BEGIN FP
A configuration is said to be {\it oriented} 
%END FP
if the following conditions hold:
\begin{enumerate}
\item All the robots are at distinct positions on the same circle $C_\OR$, except only one of them, 
called $r_\OR$, located inside $C_\OR$;
\item $r_\OR$ is not located at the center $O$ of $C_\OR$;
\item there is no robot on $C_\OR \cap [O,r_\OR)$. 
\end{enumerate}

\begin{figure}[!htbp]
\begin{center}
    \epsfig{file=OC.eps, width=0.25\linewidth}
\end{center}
\caption{An oriented configuration ($n=11$).}
\label{fig:OC}
\end{figure}

An example of an oriented configuration is shown in Figure~\ref{fig:OC} with $n=11$. 
Let us denote an oriented configuration by the pair of its two main parameters, i.e.,
$(C_\OR,r_\OR)$.  Two oriented configurations $(C^\alpha_\OR,r^\alpha_\OR)$ and 
$(C^\beta_\OR,r^\beta_\OR)$ are said to be \emph{equivalent} if
$C^\alpha_\OR = C^\beta_\OR$ and both $r^\alpha_\OR$ and $r^\beta_\OR$ are located 
at the same position.  In other words, the only possible 
difference between two equivalent 
oriented configurations $(C^\alpha_\OR,r^\alpha_\OR)$ and $(C^\beta_\OR,r^\beta_\OR)$ 
is different positions of robots between $C^\alpha_\OR$ and $C^\beta_\OR$.

We now describe Procedure~$\phi_{\OR}$ shown in Algorithm~\ref{algo:OC}.  This procedure assumes that
the configuration is oriented.  In such a configuration, we will build a partial order among the robots
to eventually form an $n$-gon.

\begin{algo}[htb]
%\begin{footnotesize}
\begin{small}
\begin{tabbing}
  xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= \kill 
\PROC{\phi_{\OR}}\\
\> $C_\OR := \mbox{circle where } n-1 \mbox{ robots are located}$;\\
\> $O:= \mbox{center of }C_\OR$;\\
\> $r_\OR := \mbox{robot inside } C_\OR$;\\
\> $p_1 := C_\OR \cap [O,r_\OR)$;\\ 
\> $PS := FindFinalPos(C_\OR ,p_1)$;\\
\> $FRS := \mbox{set of robots which are not located on a position in } PS \mbox{, except } r_\OR$;\\
\> \IF{$FRS = \emptyset$}\\
\> \THEN \> // Every robot on $C_\OR$ is located on a final position ($\in PS$).\\
\>       \> \IF{$r_i = r_{\OR}$} %// Robot $r_i$ the one inside $C_{\OR}$\\
%\>       \> 
             \THEN move to Position $p_1$;\\
\>       \> \ENDIF\\
\> \ELSE \> $EFR := ElectFreeRobots(FRS)$;\\
\>       \> \IF{$r_i \in EFR$}
%\>       \> 
            \THEN move to Position $Associate(r_i)$; %\\
%\>       \> \ENDIF\\
%\> \ENDIF\\
\end{tabbing}
\end{small}
%\end{footnotesize}
\caption{Procedure $\phi_\OR$ for any robot $r_i$ in an oriented configuration if $n\geq 5$}
\label{algo:OC}
\end{algo}

Let $p_1,\ldots,p_n$ be the final positions of the robots when the regular $n$-gon is formed.  
Let $p_1 = C_\OR \cap [O,r_\OR)$. Then,  for each $k \in 2\ldots n$, $p_k$ is the 
point on $C_\OR$ such that $\widehat{p_1 O p_k} = \frac{2k\pi}{n}$. 
Clearly, while the distributed system remains in an equivalent oriented configuration, all the final 
position remain unchanged for every robot. 
A position $p_k$,  $k \in 2\ldots n$, is said to be \emph{free} if no robot takes place at $p_k$.  Similarly, 
a robot $r_i$ on $C_\OR$ (i.e., $r_i  \neq r_\OR$) is called a \emph{free} robot if its current position 
does not belong to $\{p_2, \ldots, p_n\}$.
Define Function $FindFinalPos(C_\OR,p_1)$ which returns the set of final positions on $C_\OR$ 
with respect to $p_{1}$.  Clearly, all the robots compute the same set of final positions, stored in $PS$.  
Each robot also temporarily stores the set of free robots in the variable called $FRS$.  

Basically, if $FRS = \emptyset$ while the $n$-gon is not formed, then it remains $r_\OR$ only 
to move from its current position inside $C_\OR$ to $p_1$.  Otherwise, the robots move in waves
to the final positions following the order defined by Function $ElectFreeRobots()$.  The elected 
robots are the closest free robots from $p_1$.  
Clearly, the result of Function $ElectFreeRobots()$ return the same set of robots for 
every robot.  Also, the number of elected robots is at most
equal to $2$, one for each direction on $C_\OR$ with respect to $p_1$.  Note that it can be 
equal to $1$ when there is only one free robot, i.e., when only one robot on $C_\OR$ did
not reach the last free position.

Function $Associate(r)$ assigns a unique free position to an elected robot as follows:\newline
\noindent If $ElectFreeRobots()$ returns only one robot $r$, then $r$ is associated to the unique free
remaining position $p$.  This allows $r$ to move to $p$.  
If $ElectFreeRobots()$ returns a pair of robots $\{r_a,r_b\}$ ($r_a \ne r_b$), then the closest robot 
to $p_1$, in the clockwise (respectively, counterclockwise) is associated with the closest position to 
$p_1$ in the clockwise (resp., counterclockwise) direction.  
Note that, even if the robots may have opposite clockwise directions, $r_a$, $r_b$, and their associated 
positions are the same for every robot. 

\begin{lemma}
\label{lem:oc}
%BEGIN FP
If the robots are in an oriented configuration at time $t_j$ ($j\geq0$), then
at time $t_{j+1}$, either the robots are in an equivalent oriented configuration 
or they form a regular $n$-gon.
\end{lemma}
\begin{proof}
By contradiction, assume that starting from an oriented configuration at time $t_j$,
the robots are not in an equivalent oriented configuration and they 
do not form a regular $n$-gon at time $t_{j+1}$.  By assumption, at each time instant $t_j$,
at least one robot is active.  So, by fairness, starting from an oriented 
configuration, at least one robot executes Procedure~$\phi_{\OR}$.  Assume first that no 
robot executing Procedure~$\phi_{\OR}$ moves from $t_j$ to $t_{j+1}$.  In that case,
since the robots are located on the same positions at $t_j$ and at $t_{j+1}$, the robots 
are in the same oriented configuration at $t_{j+1}$. An oriented configuration 
being equivalent to itself, this contradicts the assumption. 
So, at least one robot moves from $t_j$ to $t_{j+1}$.  
There are two cases to consider:
\begin{enumerate}
\item  No final position is free at time $t$.  So, every robots on $C_{\OR}$ ($\neq r_\OR$) 
is located on a final position and no final position is free. 
Then, for every robot executing Procedure~$\phi_{\OR}$, $FRS= \emptyset$.  
In that case, only $r_\OR$ is allowed to move.  Since by assumption
at least one robot moves from $t_j$ to $t_{j+1}$, 
$r_\OR$ moves from its current position to $p_1$.  Therefore, the robots form a regular $n$-gon
at time $t_{j+1}$.  A contradiction.
\item Final positions are free at time $t$.  Then, for every robot executing Procedure~$\phi_{\OR}$, 
$FRS\neq \emptyset$.  By construction, there exists either one or two robots which belongs 
to the set $EFR$ and $r_\OR$ is not allowed to move.  
Therefore, at least one of them moves from its current position on $C_\OR$ to its associated 
free position.
Obviously, the robots are again in distinct positions from $t_j$ to $t_{j+1}$. Furthermore,
 since all the final positions are on $C_\OR$ and $r_\OR$ remains at the same position
from $t_j$ to $t_{j+1}$, the robots are in an equivalent oriented configuration at $t_{j+1}$.  
A contradiction.
\end{enumerate}
\end{proof}

%\begin{lemma}
%\label{lem:oc2}
%If the robots are in ideal configuration, there exists at least one robot that can move toward any final destination.
%\end{lemma}
%\begin{proof}
%There are two cases to consider:
%\begin{enumerate}
%\item Final positions are free at time $t$.  Then, for every robot executing Procedure~$\phi_{\OR}$, 
%$FRS\neq \emptyset$. trivial
%\item  No final position is free at time $t$.  So, every robots on $C_{\OR}$ ($\neq r_\OR$) 
%is located on a final position and no final position is free. 
%Then, for every robot executing Procedure~$\phi_{\OR}$, $FRS= \emptyset$.  
%In that case, only $r_\OR$ is allowed to move.
%\end{enumerate}
%\end{proof}

\begin{theorem}
\label{th:oc}
Starting from an oriented configuration, Algorithm $\phi_{oriented}$ solves the Circle Formation Problem.
\end{theorem}
\begin{proof}
It follows from the proof of Lemma~\ref{lem:oc} that in a oriented configuration, there exists 
at least one robot which can move to any final position.  The theorem follows by fairness 
and Lemma~\ref{lem:oc}.
\end{proof}
%END FP


\subsection{Main Algorithm} % for a Prime Number ($\geq5$) of Robots For any Initial Configuration  }

The main part of our solution is presented in Algorithm~\ref{algo:ngon}.  
Using Algorithm $\phi_{circle}$~\cite{DK02}, the robots are first placed in a circle $C$.  Then, 
a robot is pointed out as the leader $r_\OR$---using Function~$Elect()$ described in Subsection~\ref{sub:LE}.  
Next, Robot~$r_\OR$ moves inside the circle on the segment $[O,r_\OR]$, at a position arbitrarily chosen 
at the middle of $[O,r_\OR]$.  Finally, following the partial order provided by Procedure~$\phi_{\OR}$,
the robots eventually take place in a regular $n$-gon. 

\begin{algo}[htb]
%\begin{footnotesize}
\begin{small}
\begin{tabbing}
  xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= \kill 
\IF{the robots do not take place in a regular $n$-gon} \\
\THEN \> \IF{the robots are in an oriented configuration}\\
      \> \THEN \> Execute Procedure $\phi_{\OR}$\\
      \> \ELSE \> \IF{the robots take place in a circle $C$}\\
      \>       \> \THEN \> \IF{$r_i = Elect()$} //Robot $r_i$ is the leader robot\\
      \>       \>       \> \THEN \> move to Position $p$ such that $p = \frac{Dist(r_i,O)}{2}$, $O$ being the center of $C$;\\
      \>       \>       \> \ENDIF\\
      \>       \> \ELSE \> Execute Procedure $\phi_{circle}$;
\end{tabbing}
\end{small}
%\end{footnotesize}
\caption{Procedure $\phi_\OR$ for any robot $r_i$ in an oriented configuration if $n\geq 5$}
\caption{($\phi_{n\mbox{-gon}}$) Algorithm for any robot $r_i$ if $n\geq 5$}
\label{algo:ngon}
\end{algo}

\begin{theorem}
\label{th:ngon}
Algorithm $\phi_{n\mbox{-gon}}$ solves the problem of circle formation for $n\geq 5$ robots.
\end{theorem}
\begin{proof}
 From Algorithm~\ref{algo:ngon}, if the robots form an $n$-gon, then no robot moves and the 
the robots form an $n$-gon forever.  If the robots do not form an $n$-gon, then 
from Theorem~\ref{th:DK}, Algorithm~\ref{algo:ngon} again, Lemma~\ref{lem:LE}, and 
Theorem~\ref{th:oc}, the robots eventually form an $n$-gon.
\end{proof}

\section{Conclusion}
%\FIXME{A voir: parler de la snap.?  A prori, non.}
We showed how Lyndon words can be used in the distributed control of a set of $n$ anonymous robots being
memoryless, without any common sense of direction, and unable to communicate in an other way than observation. 
An efficient and simple deterministic protocol to form a regular $n$-gon was presented for
a prime number of robots.  We believe that the new idea presented in this paper should help in the 
design of the protocol for the Circle Formation Problem with any arbitrary number of robots.  
That would be the main goal of our future research.

\section*{Acknowledgements}
We are grateful to Gw\'ena\"el Richomme for the valuable discussions.

%\begin{footnotesize}
\begin{small}
\bibliographystyle{alpha}
\bibliography{prime}
\end{small}
%\end{footnotesize}

\newpage
\appendix
\section{Appendix : Circle Formation for $3$ Robots}
The aim of the algorithm, shown in Algorithm~\ref{algo:3gon}, is to lead the $3$ robots to eventually
take place in a regular $3$-gon, i.e., an equilateral triangle.  
The correctness proof of Algorithm~\ref{algo:3gon} is based on the following lemma: 
\begin{lemma}
\label{lem:3gon}
If the three robots $\{r_1,r_2,r_3\}$ do not form an equilateral triangle, then it is possible to elect only one robot among them.
\end{lemma}
\begin{proof}
If $\{r_1,r_2,r_3\}$ do not form 
an equilateral triangle, then either (Case~$1$) they belongs to the same line, (Case~$2$) they form an isosceles 
triangle, or (Case~$3$) they form an ordinary triangle.  In the first case, the elected robot is 
the median one, which is unique.  In Case~$2$, the elected robot is the one placed at the unique angle different
from the two others.  In Case~$3$, there exists a unique angle which is strictly smallest than the others.  The 
elected robots is the one placed at this unique angle. 
\end{proof}

Lemma~\ref{lem:3gon} allows to define the Boolean function $Elect()$, which can be executed by any robots $r_i$.  
$Elect()$ returns the unique leader robot according to Lemma~\ref{lem:3gon}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%    ALGO : 3GON                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algo}[htb]
%\begin{footnotesize}
\begin{small}
\begin{tabbing}
  xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= xxxxx \= \kill 
\IF{the robots do not take place in a regular $3$-gon} \\
\THEN \> \IF{$r_i = Elect()$}\\
      \> \THEN \> $(r_j,r_k)$ denotes the two other robots than myself;\\
      \>       \> move to Position $p$ such that $\{p,r_j,r_k\}$ form a regular $3$-gon;
\end{tabbing}
\end{small}
%\end{footnotesize}
\caption{($\phi_{3\mbox{-gon}}$) Algorithm for any robot $r_i$ if $n=3$}
\label{algo:3gon}
\end{algo}

\begin{theorem}
\label{theorem1}
Algorithm $\phi_{3\mbox{-gon}}$ solves the problem of circle formation for three robots.
\end{theorem}
\begin{proof}
 From Lemma \ref{lem:3gon}, we can distinguish a unique robot, called the leader.
According to Algorithm~\ref{algo:3gon}, if the robots do not form an equilateral triangle at time $t$, then only 
the leader is allowed to move.  Since by assumption at least one robot is activated at each instant time, 
at time $t+1$ the robots form an equilateral triangle. 
\end{proof}

\end{document}

LaRIARR-2006-05.bbl
\begin{thebibliography}{FPSW99}

\bibitem[Che04]{C04}
M~Chemillier.
\newblock Periodic musical sequences and lyndon words.
\newblock {\em Soft Computing}, 8(9):611--616, 2004.

\bibitem[CMN04]{CMN04}
I~Chatzigiannakis, M~Markou, and S~Nikoletseas.
\newblock Distributed circle formation for anonymous oblivious robots.
\newblock In {\em 3rd Workshop on Efficient and Experimental Algorithms}, pages
  159--174, 2004.

\bibitem[CP02]{CP02}
M~Cieliebak and G~Prencipe.
\newblock Gathering autonomous mobile robots.
\newblock In {\em 9th International Colloquium on Structural Information and
  Communication Complexity (SIROCCO 9)}, pages 57--72, 2002.

\bibitem[Deb95]{D95}
X~A Debest.
\newblock Remark about self-stabilizing systems.
\newblock {\em Communications of the ACM}, 38(2):115--117, 1995.

\bibitem[DK02]{DK02}
X~Defago and A~Konagaya.
\newblock Circle formation for oblivious anonymous mobile robots with no common
  sense of orientation.
\newblock In {\em 2nd ACM International Annual Workshop on Principles of Mobile
  Computing (POMC 2002)}, pages 97--104, 2002.

\bibitem[Dol00]{D00}
S.~Dolev.
\newblock {\em Self-Stabilization}.
\newblock The MIT Press, 2000.

\bibitem[DR04]{DR04}
O~Delgrange and E~Rivals.
\newblock Star: an algorithm to search for tandem approximate repeats.
\newblock {\em Bioinformatics}, 20(16):2812--2820, 2004.

\bibitem[FPSW99]{FPSW99}
P~Flocchini, G~Prencipe, N~Santoro, and P~Widmayer.
\newblock Hard tasks for weak robots: The role of common knowledge in pattern
  formation by autonomous mobile robots.
\newblock In {\em 10th Annual International Symposium on Algorithms and
  Computation (ISAAC 99)}, pages 93--102, 1999.

\bibitem[Kat05]{K05}
B~Katreniak.
\newblock Biangular circle formation by asynchronous mobile robots.
\newblock In {\em 12th International Colloquium on Structural Information and
  Communication Complexity (SIROCCO 2005)}, pages 185--199, 2005.

\bibitem[Lot83]{L83}
M~Lothaire.
\newblock {\em Combinatorics on words}.
\newblock Addison-Wesley, 1983.

\bibitem[Pre02]{P02}
G~Prencipe.
\newblock Distributed coordination of a set of autonomous mobile robots.
\newblock Technical Report TD-4/02, Dipartimento di Informatica, University of
  Pisa, 2002.

\bibitem[SM90]{SM90}
R~Siromoney and L~Mathew.
\newblock A public key cryptosystem based on lyndon words.
\newblock {\em Information Processing Letters}, 35(1):33--36, 1990.

\bibitem[SS90]{SS90}
K~Sugihara and I~Suzuki.
\newblock Distributed motion coordination of multiple mobile robots.
\newblock In {\em IEEE International Symosium on Intelligence Control}, pages
  138--143, 1990.

\bibitem[SS96]{SS96}
K~Sugihara and I~Suzuki.
\newblock Distributed algorithms for formation of geometric patterns with many
  mobile robots.
\newblock {\em Journal of Robotic Systems}, 3(13):127--139, 1996.

\bibitem[SY96]{SY96}
I~Suzuki and M~Yamashita.
\newblock Agreement on a common $x$-$y$ coordinate system by a group of mobile
  robots.
\newblock {\em Intelligent Robots: Sensing, Modeling and Planning}, pages
  305--321, 1996.

\bibitem[SY99]{SY99}
I~Suzuki and M~Yamashita.
\newblock Distributed anonymous mobile robots - formation of geometric
  patterns.
\newblock {\em SIAM Journal of Computing}, 28(4):1347--1363, 1999.

\end{thebibliography}
