E. Domenjoud, X. Provençal and L. Vuillon ``Palindromic language of thin discrete planes '' TCS to appear

We work on the Reveill`es hyperplane P(v, 0, omega) with normal vector v in Rd, shift mu = 0 and
thickness omega in R. Such a hyperplane is connected as soon as omega is
greater than some value _(v,0), called the connecting thickness of v with null
shift. In the case where v satisfies the so called Kraaikamp and Meester
criterion, at the connecting thickness the hyperplane has very specific
properties. First of all the adjacency graph of the voxels forms a tree. This
tree appeared in many works both in discrete geometry and in discrete dynamical
systems. In addition, it is well known that for a finite coding of length n of
discrete lines, the number of palindromes in the language is exactly n + 1. We
extend this notion of language to labeled trees and we compute the number of
distinct palindromes. In fact for our voxel adjacency trees with n letters we
show that the number of palindromes in the language is also n+1. This result
establishes a first link between combinatorics on words, palindromic languages,
voxel adjacency trees and connecting thickness of Reveill`es hyperplanes. It
also provides a better understanding of the combinatorial structure of discrete
planes.

X. Provençal and L. Vuillon ``Discrete segments of Z3 constructed by synchronization of words'' Discrete Applied Mathematics, Volume 183, 11 March 2015, Pages 102-117

We study a natural and naive composition
algorithm what takes three input words written on two-letter alphabets and
synchronizes then into a word on a three-letter alphabet. We show that in the
case where the three input words are compatible Christoffel words, the
algorithm provides a synchronization of the letters what allows the geometrical
interpretation of the input words to be inherited by the output word forming a
3D discrete line segment. A second approach is considered while applying our
composition algorithm to words defined by stripes meeting at a
corner of a discrete planes. We show that, under certain conditions, the output
of the algorithm correspond to the normal vector of the plane.

L. Vuillon and C. Lesieur ``From local to global changes in proteins: a network view'' Current Opinion in Structural Biology Volume 31, April 2015, Pages 1–8

To fulfill the biological activities in
living organisms, proteins are endowed with dynamics, robustness and
adaptability. The three properties co-exist because they allow global changes
in structure to arise from local perturbations (dynamics). Robustness refers to
the ability of the protein to incur such changes without suffering loss of
function; adaptability is the emergence of a new biological activity. Since
loss of function may jeopardize the survival of the organism and lead to
disease, adaptability may occur through the combination of two local
perturbations that together rescue the initial function. The review highlights
the relevancy of computational network analysis to understand how a local
change produces global changes.

C. Lesieur and L. Vuillon ``From Tilings to Fibers – Bio-mathematical Aspects of Fold Plasticity'' Oligomerization of Chemical and Biological Compounds, Dr. Claire Lesieur (Ed.), ISBN: 978-953-51-1617-2, InTech, DOI: 10.5772/58577.

Protein oligomers are made by the
association of protein chains via intermolecular amino acid interactions
(interaction between subunits) forming so called protein interfaces. This
chapter proposes mathematical concepts to investigate the shape constraints on
the protein interfaces in order to promote oligomerization. First, we focus on
tiling the plane (2 dimensions) by translation with abstract shapes. Using the
fundamental Theorem of Beauquier-Nivat, we show that the shapes of the tiles
must be either like a square or like a hexagon to tile the whole plane. Second,
we look in more details at the tiling of a cylinder and discuss its relevancy
in constructing protein fibers. The universality of such “building” properties
are investigated through biological examples. This chapter is written four-hand
by a mathematician and a biologist in order to present bio-mathematical aspects
of fiber constructions.

G. Feverati, M. Achoch, L. Vuillon and C. Lesieur ``Intermolecular β-Strand Networks Avoid Hub Residues and Favor Low Interconnectedness: A Potential Protection Mechanism against Chain Dissociation upon Mutation'' PLOS ONE 10.1371/journal.pone.0094745

Altogether few protein oligomers undergo
a conformational transition to a state that impairs their function and leads to
diseases. But when it happens, the consequences are not harmless and the
so-called conformational diseases pose serious public health problems.
Notorious examples are the Alzheimer's disease and some cancers associated with
a conformational change of the amyloid precursor protein (APP) and of the p53 tumor
suppressor, respectively. The transition is linked with the propensity of β-strands
to aggregate into amyloid fibers. Nevertheless, a huge number of protein
oligomers associate chains via β-strand interactions (intermolecular β-strand
interface) without ever evolving into fibers. We analyzed the layout of 1048
intermolecular β-strand interfaces looking for features that could provide the β-strands
resistance to conformational transitions. The interfaces were reconstructed as
networks with the residues as the nodes and the interactions between residues
as the links. The networks followed an exponential decay degree distribution,
implying an absence of hubs and nodes with few links. Such layout provides
robustness to changes. Few links per nodes do not restrict the choices of amino
acids capable of making an interface and maintain high sequence plasticity. Few
links reduce the “bonding” cost of making an interface. Finally, few links
moderate the vulnerability to amino acid mutation because it entails limited
communication between the nodes. This confines the effects of a mutation to few
residues instead of propagating them to many residues via hubs. We propose that
intermolecular β-strand interfaces are organized in networks that tolerate
amino acid mutation to avoid chain dissociation, the first step towards fiber
formation. This is tested by looking at the intermolecular β-strand network of
the p53 tetramer.

A. Casagrande, H. Lesca et L. Vuillon ``Un outil pour surmonter la surcharge d’information de la veille stratégique'' Colloque VSST Nancy (France), 23-25 octobre 2013, 17p.

Dans cette communication, nous proposons
le concept d’« informations voisines », nous indiquons son utilité dans le
processus de veille anticipative stratégique (VAS), face au problème de la
surcharge d’information notamment occasionnée par l’usage de l’Internet. Nous
présentons un prototype d’outil informatique visant à instrumenter le concept
ainsi qu’un cas d’application. Le concept est particulièrement utile lorsque
la veille stratégique est orientée « exploitation des informations à
caractère anticipatif » pour l’anticipation, ceux-ci étant généralement
noyés dans de gros volumes de données. Nous expérimentons notre prototype
sur la problématique de la valorisation du CO2 et nous montrons ainsi que cet
outil permet un réel gain de temps pour rendre utilisable les informations
collectées, par les décideurs.

G. Feverati, C. Lesieur and L. Vuillon ``SYMMETRIZATION: RANKING AND CLUSTERING IN PROTEIN INTERFACES'' Mathematics of Distances and Applications.

Purely geometric arguments are used to
extract information from three-dimensional structures of oligomeric proteins,
that are very common biological entities stably made of several polypeptidic
chains. They are characterized by the presence of an interface between adjacent
amino acid chains and can be investigated with the approach proposed here. We
introduce a method, called symmetrization, that allows one to rank interface
interactions on the basis of inter-atomic distances and of the local geometry.
The lowest level of the ranking has been used previously with interesting
results. Now, we need to complete this picture with a careful analysis of the
higher ranks, that are for the first time introduced here, in a proper
mathematical set up. The interface finds a very nice mathematical abstraction
by the notion of weighted bipartite graph, where the inter-atomic distance
provides the weight. Thus, our approach is partially inspired to graph theory decomposition methods but with an emphasis to “locality”,
namely the idea that structures constructed by the symmetrization adapt to the
local scales of the problem. This is an important issue as the known interfaces
may present major differences in relation to their size, their composition and
the local geometry. Thus, we looked for a local method, that can autonomously
detect the local structure. The physical neighborhood is introduced by the
concept of cluster of interactions. We discuss the biological applications of
this ranking and our previous fruitful experience with the lowest symmetrized
level. An example is given, using the prototypical cholera toxin.

E. Domenjoud and L. Vuillon ``Geometric palindromic closure'' uniform distribution theory 7 (2012), no. 2, 109-140.

We de fine, through a set of symmetries,
an incremental construc- tion of geometric objects in Zd. This construction is
directed by a word over the alphabet {1,...,d}. These
objects are composed of d disjoint components linked by the origin and enjoy
the nice property that each component has a central sym- metry as well as the
global object. This construction may be seen as a geometric palindromic
closure. Among other objects, we get a 3 dimensional version of the Rauzy
fractal. For the dimension 2, we show that our construction codes the standard
discrete lines and is equivalent to the well known palindromic closure in
combinatorics on words.

A. Blondin massé, G. Paquin, H. Tremblay and L. Vuillon ``On Generalized Pseudostandard Words Over Binary Alphabets'' Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.11

In this paper, we study generalized
pseudostandard words over a two-letter alphabet, which extend the classes of
standard Sturmian, standard episturmian and pseudostandard words, allowing
different involutory antimorphisms instead of the usual palindromic closure or
a fixed involutory antimorphism. We first discuss pseudoperiods, a useful tool
for describing words obtained by iterated pseudopalindromic closure. Then, we
introduce the concept of normalized directive bi-sequence (Θ, w) of a
generalized pseudostandard word, that is the one that exactly describes all the
pseudopalindromic prefixes of it. We show that a directive bi-sequence is normalized
if and only if its set of factors does not intersect a finite set of forbidden
ones. Moreover, we provide a construction to normalize any directive
bi-sequence. Next, we present an explicit formula, generalizing the one for the
standard episturmian words introduced by Justin, that computes recursively the
next prefix of a generalized pseudostandard word in term of the previous one.
Finally, we focus on generalized pseudostandard words having complexity 2n,
also called Rote words. More precisely, we prove that the normalized
bi-sequences describing Rote words are completely characterized by their
factors of length 2.

G. Feverati, M. Achoch, J. Zrimi, L. Vuillon and C. Lesieur ``Beta-Strand Interfaces of Non-Dimeric Protein Oligomers Are Characterized by Scattered Charged Residue Patterns'' PLoS ONE 7(4): e32558.

Protein oligomers are formed either
permanently, transiently or even by default. The protein chains are associated
through intermolecular interactions constituting the protein interface. The
protein interfaces of 40 soluble protein oligomers of stœchiometries above two
are investigated using a quantitative and qualitative methodology, which analyzes
the x-ray structures of the protein oligomers and considers their interfaces as
interaction networks. The protein oligomers of the dataset share the same
geometry of interface, made by the association of two individual β-strands (β-interfaces),
but are otherwise unrelated. The results show that the β-interfaces are made of
two interdigitated interaction networks. One of them involves interactions
between main chain atoms (backbone network) while the other involves
interactions between side chain and backbone atoms or between only side chain
atoms (side chain network). Each one has its own characteristics which can be
associated to a distinct role. The secondary structure of the β-interfaces is
implemented through the backbone networks which are enriched with the
hydrophobic amino acids favored in intramolecular β-sheets (MCWIV). The
intermolecular specificity is provided by the side chain networks via
positioning different types of charged residues at the extremities (arginine)
and in the middle (glutamic acid and histidine) of the interface. Such charge
distribution helps discriminating between sequences of intermolecular β-strands,
of intramolecular β-strands and of β-strands forming β-amyloid fibers. This
might open new venues for drug designs and predictive tool developments.
Moreover, the β-strands of the cholera toxin B subunit interface, when produced
individually as synthetic peptides, are capable of inhibiting the assembly of
the toxin into pentamers. Thus, their sequences contain the features necessary
for a β-interface formation. Such β-strands could be considered as ‘assemblons’,
independent associating units, by homology to the foldons (independent folding
unit). Such property would be extremely valuable in term of assembly inhibitory
drug development.

I. Gambini and L. Vuillon ``How many faces can polycubes of lattice tilings by translation of R3 have?'' Electronic Journal of Combinatorics, P199, 2011

We construct a class of polycubes that
tile the space by translation in a latticeperiodic way and show that for this
class the number of surrounding tiles cannot be bounded. The first construction
is based on polycubes with an L-shape but with many distinct tilings of the
space. Nevertheless, we are able to construct a class of more complicated
polycubes such that each polycube tiles the space in a unique way and such that
the number of faces is 4k + 8 where 2k + 1 is the volume of the polycube. This
shows that the number of tiles that surround the surface of a space-filler
cannot be bounded.

I. Gambini and L. Vuillon ``Non lattice periodic tilings of R3 by single polycubes'' To appear in Theoretical Computer Science 2012

In this paper, we study a class of
polycubes that tile the space by translation in a non
lattice periodic way. More precisely, we construct a family of tiles indexed by
integers with the property that Tk is a tile having k >= 2 has anisohedral
number. That is k copies of Tk are assembled by translation in order to form a
metatile. We prove that this metatile is lattice periodic while Tk is not a
lattice periodic tile.

A. Frosini, S. Rinaldi, K. Tawbe and L. Vuillon ``Reconstruction of 2-convex polyominoes'' LAMA research report

A polyomino P is called 2-convex if for
every two cells belonging to P , there ex- ists a
monotone path included in P with at most two changes of direction. This paper
studies the tomographical aspects of 2-convex polyominoes from their hori-
zontal and vertical pro jections and gives an algorithm that reconstructs all
2-convex polyominoes in polynomial time.

D. Jamet , G. Paquin, G. Richomme and L. Vuillon ``On the fixed points of the iterated pseudopalindromic closure'' Theoretical Computer Science 412, Issue 27, 2974-2987, 2011, special issue "Combinatorics on Words (WORDS 2009), 7th International Conference on Words"

First introduced in the study of the
Sturmian words, the iterated palindromic closure was generalized to
pseudopalindromes. This operator allows one to construct words with infinitely
many pseudopalindromic prefixes, called pseudostandard words. We provide here
several combinatorial properties of the fixed points under the iterated
pseudopalindromic closure.

A. Blondin Massé , S. Brlek, S. Labbé and L. Vuillon ``Palindromic complexity of codings of rotations'' Theoret. Comput. Sci. 412 (2011) 6455-6463.

We study the structure of inﬁnite words
obtained by coding rotations on partitions of the unit circle by inspecting the
return words. The main result is that every factor of a coding of rotations on
two intervals has at most 4 complete return words, where the bound is realized
only for a ﬁnite number of factors. As a byproduct we obtain that when the
partition consists of two intervals, then the corresponding word is full, that
is, it realizes the maximal palindromic complexity. We also provide a
combinatorial proof for the special case of complementary-symmetric Rote
sequences by considering both the palindromes and the antipalindromes occurring
in it.

E. Domenjoud , D. Jamet , D. Vergnaud and L. Vuillon ``Enumeration Formula for (2, n)-Cubes in Discrete Planes'' Discrete applied mathematics 160, 15 (2012) 2158-2171

We compute the number of local conﬁgurations
of size 2 ×n on naive discrete planes using combinatorics on words,
2-dimensional Rote sequences and Berstel-Pocchiola diagrams.

In this article, we describe a general
method for constructing various shapes of convex polyominoes using DNA Wang
tiles. we recall the basic definitions and notations
of two-dimensional languages and tiling systems and some basic definitions on
polyominoes, in particular the definitions of convex, directed-convex, and
parallelogram polyominoes. We describe the algorithm to transform tiles of a
tiling system into labelled Wang tiles. We show explicitly the set of labelled
Wang tiles that allows us to construct convex polyominoes. We give an example
of a parallelogram polyomino built on labelled Wang tiles. The last part
concerns the transformation of labelled Wang tiles into DNA Wang tiles.
Moreover, we show that it is possible to control the size of the polyominoes to
be constructed, by means of a DNA strand.

K. Tawbe, F. Cotton and L. Vuillon ``Evolution of Brain Tumor and Stability of Geometric Invariants’’ International Journal of Telemedicine and Applications Volume 2008 (2008), Article ID 210471, 12 pages

**This
paper presents a method to reconstruct and to calculate geometric invariants on
brain tumors. The geometric invariants considered in the paper are the volume,
the area, the discrete Gauss curvature, and the discrete mean curvature. The
volume of a tumor is an important aspect that helps doctors to make a medical
diagnosis. And as doctors seek a stable calculation,
we propose to prove the stability of some invariants. Finally, we study the
evolution of brain tumor as a function of time in two or three years depending
on patients with MR images every three or six months.**

P. Domosi, G. Horvath and L. Vuillon ``On Shyr-Yu Theorem'' Theoretical Computer Science, Volume 410 (2009)

**An alternative proof of Shyr-Yu Theorem
is given. Some generaliza- tions are also considered using fractional root
decompositions and frac- tional exponents of words. **

**It is well-known that Sturmian sequences
are the non ultimately periodic sequences that are balanced over a 2-letter
alphabet. They are also characterized by their complexity: they have exactly
$(n+1)$ distinct factors of length $n$. A natural
generalization of Sturmian sequences is the set of infinite episturmian
sequences. These sequences are not necessarily balanced over a $k$-letter
alphabet, nor are they necessarily aperiodic. In this paper, we characterize
balanced episturmian sequences, periodic or not, and prove Fraenkel's
conjecture for the special case of episturmian sequences. It appears that
balanced episturmian sequences are all ultimately periodic and they can be
classified in 3 families. **

S. Brlek, A. Frosini, S. Rinaldi and L. Vuillon ``Tilings by translation: enumeration by a rational langage approach'' Electronic Journal of Combinatorics Volume 13 (1), 2006.

**Theoretical Computer Science, Volume
319, Issues 1-3, Pages 1-484 (10 June 2004). **

**We describe some combinatorial
properties of an intriguing class of infinite words connected with the one
defined by Kolakoski, defined as the fixed point of the run-length encoding
$\Delta$. It is based on a bijection on the free monoid over $\Sigma =\{ 1,2\}$, that shows some surprising mixing properties. All
words contain the same finite number of square factors, and consequently they
are cube-free. This suggests that they have the same complexity as confirmed by
extensive computations. We further investigate the occurrences of palindromic
subwords. Finally we show that there exist smooth words obtained as fixed
points of substitutions (realized by transducers) as in the case of $K$. **

C. Frougny and L. Vuillon ``Coding of two-dimensional constraints of finite type by substitutions'' JALC, 2005,volume 10 (4) pages 465-482.

**We give an automatic method to generate
transition matrices associated with two-dimensional contraints of finite type
by using squared substitutions of constant dimension. **

A. Frosini, M. Nivat and L. Vuillon ``An introductive analysis of periodical discrete sets from a tomographical point of view'' Theoretical Computer Science

** In this paper we introduce a new
class of binary matrices whose entries show periodical configurations, and we
furnish a first approach to their analysis from a tomographical point of view.
In particular we propose a polynomial-time algorithm for reconstructinf
matrices with a special periodical behavior from their horizontal and vertical
projections. We succeeded in our aim by using reductions involving polyominooes
which can be characterized by means of 2-SAT formulas. **

I. Gambini and L. Vuillon ``An algorithm for deciding if a polyomino tiles the plane by translations'' Theoret. Informatics Appl. 41, 147-155 (2007).

**For polyominoes coded by their boundary
word, we describe a quadratic $O(n^2)$ algorithm
in the boundary length $n$ which improves the naive $O(n^4)$ algorithm.
Techniques used emanate from algorithmics, discrete geometry and combinatorics
on words.**

** **

F. Chavanon, M. Latapy, M. Morvan, E. Rémila and L. Vuillon ``Graph encoding of 2D-gon tilings'' Theoretical Computer Science

**2D-gon tilings with parallelograms are a
model used in physics to study quasicrystals, and they are also important in
combinatorics for the study of aperiodic structures. In this paper, we study
the graph induced by the adjacency relation between tiles. This relation can
been used to encode simply and efficiently 2D-gon tilings for algorithmic
manipulation. We show for example how it can be used to sample random 2D-gon
tilings. **

B. Durand and L. Vuillon Editors of the Special Issue of TCS on ``Tilings of the Plane''

**Theoretical Computer Science, Volume
303, Issues 2-3, Pages 265-554 (15 July 2003). **

L. Vuillon ``Balanced words'' Bull. Belg. Math. Soc. Simon Stevin 10 (2003), no. 5, 787-805.

**This article presents a survey about
balanced words. The balance property provides from combinatorics on words and
is used as a characteristic property of the well-known Sturmian words. The main
goal of this survey is to study various generalizations of this notion with
applications and with open problems in number theory and in theoretical
computer science. We also prove a new result about the balance property of
hypercubic billiard words. **

A. Del Lungo, A. Frosini, M. Nivat and L. Vuillon ``Discrete tomography: reconstruction under periodicity constraints'' Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, Springer, Lecture Notes in Computer Science, volume 2380,(2002), 38-56.

**We study the reconstruction problem on
some new classes consisting of binary matrices with periodicity properties, and
we propose a polynomial-time algorithm for reconstructing these binary matrices
from their othogonal discrete X-rays. **

P. Hubert and L. Vuillon ``Complexity of cutting words on regular tilings'' European Journal of Combinatorics, Volume 28 , Issue 1, table of contents Pages: 429 - 438, 2007 .

**We show that the complexity of a cutting
word $u$ in a regular tiling by a polyomino $Q$ is equal to $P_n(u)= (p+q-1)n +1$ for all $n \geq 0,$ where $P_n(u)$ counts
the number of distinct factors of length $n$ in the infinite word $u$ and where
the boundary of $Q$ is constructed by $2p$ horizontal and $2q$ vertical unit
segments. **

J. Berstel and L. Vuillon ``Coding rotations on intervals'' Theoretical Computer Science 281, (2002), 99-107.

**We show that the coding of rotation by
$\alpha$ on m intervals with rationally independent lengths can be recoded over
m Sturmian words of angle $\alpha.$ More precisely,
for a given m an universal automaton is constructed such that the edge indexed
by the vector of values of the ith letter on each Sturmian word gives the value
of the ith letter of the coding of rotation. **

C. Magnien, H. D. Phan and L. Vuillon `` Characterization of lattices induced by (extended) chip firing games'' Discrete mathematics and theoretical computer science procedings AA (DM-CCG), 2001, 229-244.

**The Chip Firing Game (CFG) is a discrete
dynamical model used in physics, computer science and economics. It is known
that the set of configurations reachable from an initial configuration can be
ordered as a lattice. We first present a structural result about this model,
which allow us to introduce some useful tools for describing those lattices.
Then we establish that the class of lattices that are the configuration space
of a CFG is strictly between the class of distributive lattices and the class
of upper locally distributive (ULD) lattices. Finally we propose an extension
of the model, the coloured Chip Firing Game, which generates exactly the class
of ULD lattices. **

L. Vuillon ``On the number of return words in infinite words constructed by interval exchange transformations''

**In this article, we count the number of
return words in some infinite words with complexity $2n+1$. We also consider
some infinite words given by codings of rotation and interval exchange
transformations on $k$ intervals. We prove that the number of return words over
a given word $w$ for these infinite words is exactly $k.$
**

J. Justin and L. Vuillon ``Return words in Sturmian and episturmian words'' Theoretical Informatics and Applications 34 (2000) 343-356.

**Considering each occurence of a word $w$
in a reccurent infinite word, we define the set of return words of $w$ to be
the set of all distinct words beginning with an occurence of $w$ and ending
exactly just before the next occurence of $w$ in the infinite word. We give a
simpler proof of the recent result (of the second author) that for each factor
$w$ of a Sturmian word there exist exactly two return words of $w.$ Then, considering episturmian infinite words, which are a
natural generalization of Sturmian words, we study the position of the
occurrences of any factor in such infinite words and we determinate the return
words. At last, we apply these results in order to get a kind of balance
property of episturmian words and to calculate the recurrence function of these
words. **

I. Fagnot and L. Vuillon ``Generalized balances in Sturmian words'' Discrete Applied Mathematics, Volume 121, Issues 1-3, (2002), 83-101.

**One of the numerous characterizations of
Sturmian words is based on the notion of balance. An infinite word x on the
{0,1} alphabet is balanced if, given two factors w and w' of x having the same
length, the difference between the number of 0 in w (denoted by |w|0) and the
one of w' is at most 1, i.e. ||w|0 - |w'|0| <= 1. It is well known that a
word is Sturmian if and only if it is balanced. In this paper, the balance
notion is generalized by considering the number of occurrences of a word u in w
(denoted by |w|u) and w'. The following is obtained **

**Theorem Let x be a
Sturmian word. Let u, w and w' be three factors of x. If |w|=|w'|, we have |
|w|u - |w'|u | <= |u|. **

**We will also give
another balance property called equilibrium. This notion permits us to give a new
characterization of Sturmian words. The proofs use word graphs and return words
technics. **

L. Vuillon ``A characterisation of Sturmian words by return words'' European Journal of Combinatorics (2001) 22, 263-275.

**We present a new characterization of
Sturmian sequences using return words. Considering each occurrence of a word
$w$ in a recurrent sequence, we define the set of return words over $w$ to be
the set of all distinct words beginning with an occurrence of $w$ and ending
with the next occurrence of $w$ in the sequence. It is shown that a sequence is
a Sturmian sequence if and only if for each non empty word $w$ appearing in the
sequence the cardinality of the set of return words over $w$ is equal to two. **

V. Berthé and L. Vuillon ``Palindromes and two-dimensional Sturmian sequences'' J. Autom. Lang. Comb., 6 (2001), 121--138.

**This paper introduces a two-dimensional
notion of palindrome for rectangular factors of double sequences: these
palindromes are defined as centrosymmetric factors. This notion provides a
characterization of two-dimensional Sturmian sequences in terms of
two-dimensional palindromes, generalizing to double sequences the results in
the article of X. Droubay and G. Pirillo. **

V. Berthé et L. Vuillon ``Suites doubles de faible complexité'' Journal de Theorie des Nombres de Bordeaux 12 (2000), 179-208.

**Nous donnons une représentation
géométrique des suites doubles uniformément récurrentes de fonction de
complexité rectangulaire $mn+n$. Nous montrons que ces suites codent l'action
d'une $Z^2$-action définie par deux rotations irrationnelles sur le cercle
unité. La preuve repose sur une étude des suites doubles dont les lignes sont
des suite sturmiennes de m\^eme langage. **

J. Mairesse and L. Vuillon ``Optimal Sequences in a Heap Model with Two Pieces'' Theoret. Comput. Sci. 270 1-2 (2002), 525-560.

**In a heap model, solid blocks, or
pieces, pile up according to the Tetris game mechanism. An optimal sequence is
an infinite sequence of pieces minimizing the asymptotic growth rate of the
heap. In a heap model with two pieces, we prove that there always exists an
optimal sequence which is either periodic or Sturmian. We completely
characterize the cases where the optimal is periodic and the ones where it is
Sturmian. The proof is constructive, providing an explicit optimal sequence. We
also consider the model where the successive pieces are choosen at random,
independently and with some given probabilities. We study the expected growth
rate of the heap. For a model with two pieces, the rate is either computed
explicitly or given as an infinite series. We show an application for a system
of two processes sharing a resource, and we prove that a greedy schedule is not
always optimal. **

L. Vuillon ``Local configurations in discrete planes'' Bull. Belg. Math. Soc. 6 (1999), 625-636.

**We study the number of local
configurations in a discrete plane. We convert this problem into a computation
of a double sequence complexity. We compute the number
$C(n,m)$ of distinct $n\times m$ patterns appearing in
a discrete plane. We show that $C(n,m)=nm$ for all $n$
and $m$ positive integers. The coding of this sequence by a $Z^2$-action on the
unidimensional torus gives information about the structure of a discrete plane.
Furthermore, this sequence is a generalized Rote sequence with complexity $P(n,m)=2nm$ for all $n$ and $m$ positive integers and with a
symmetric complementary language for rectangular words. **

V. Berthé and L. Vuillon "Tilings and rotations: a two-dimensional generalization of Sturmian sequences'' Discrete Math. 223 (2000), 27-53.

**We study a two-dimensional
generalization of Sturmian sequences corresponding to an approximation of a
plane: these sequences are defined on a three-letter alphabet and code a
two-dimensional tiling obtained by projecting a discrete plane. We show that
these sequences code a $Z^2$-action generated by two rotations on the unit
circle. We first deduce a new way of computing the rectangle complexity
function. Then we provide an upper bound on the number of frequencies of
rectangular factors of given size. **

L. Vuillon ``Combinatoire des motifs d'une suite sturmienne bidimensionnelle'' Theoret. Comput. Sci. 209 (1998), no. 1-2, 261-285.

**avec**** les figures ****Figure 1 ****,****Figure 2 ****,****Figure 3 ****,****Figure 4 ****,****Figure 5 ****. Nous étudions une généralisation des
suites sturmiennes en construisant une ``surface plissée", donnée par
l'approximation d'un plan par trois sortes de faces carrées orientées suivant
les trois plans de coordonnées. \`A cette surface, on associe par projection un
pavage du plan par trois sortes de losanges. On définit sur ce pavage une
fonction de complexité en comptant le nombre de motifs distincts d'une fen\^{e}tre de taille donnée. Nous donnons, en étudiant les
prolongements des motifs, la forme explicite de cette fonction dans le cas
d'une fen\^{e}tre triangulaire et d'une fen\^{e}tre en
forme de parallélogramme. **

**Habilitation à diriger des recherches,
Université Paris VII, 28 novembre 2001 : ****``Mots infinis, suites doubles et
pavages'' **

**de**** 1993 à 1996, thèse à l'Institut de
Mathématiques de Luminy (Aix-Marseille II), sous la direction du Professeur G.
RAUZY: **

**La thèse a été financée par le CNRS /
MRE / DRET de Septembre 1994 à Septembre 1996: Bourse de Docteur Ingénieur. **