[CPM-SPIRE-L] Master Intership in Computer Science in Normandy, France

[Thierry Lecroq]

Master Intership in Computer Science
NormaSTIC
GREYC -- LITIS
Supervisors : Julien David and Thierry Lecroq

Lyndon Words and Cartesian Trees
Date: Spring 2024

Lyndon words are lexicographically smaller than all their non-empty proper suffixes.
The Lyndon array of a word gives, for each position of the word,
 the length of the longest Lyndon word starting at that position.

The Cartesian tree of a sequence s of m numbers is defined as follows:
- the root is the index i of the smallest element in s (the index of the first minimal element
 if it is not unique);
- the left subtree of the root is the Cartesian tree of s[0..i-1];
- the right subtree of the root is the Cartesian tree of s[i+1..m-1].

The exist several linear representations of Cartesian trees.

The Lyndon array of a word x can be computed with the Cartesian tree of the inverse suffix array
 of x.
 
The goals of this internship are:
- list all the known methods for computing Lyndon arrays;
- list all the known linear representations of Cartesian trees;
- select the linear representations than can enable to efficiently compute
 Lyndon arrays.

This internship fit into the activities of the Lyndex projet funded by the NormaSTIC CNRS FR 3638 federation.
The results of this internship will feed the web site of the project lyndex.org.

Full description available here: https://lyndex.org/stage/stage-en.pdf

Contacts: 

julien.david at unicaen.fr

Thierry.Lecroq at univ-rouen.fr

-- 
Thierry Lecroq, http://monge.univ-mlv.fr/~lecroq, LITIS EA 4108, CURIB, UFR Sciences et Techniques, Univ. de Rouen Normandie F-76821 Mont-Saint-Aignan Cedex,Tel: +33 2 3514 6013