**B. Colange, L. Vuillon, S. Lespinats, D. Dutykh** Interpreting Distortions in Dimensionality Reduction by Superimposing Neighbourhood Graphs
. * Paper presented at IEEE VIS 2019 Conference. *

To perform visual data exploration, many dimensionality reduction methods have been developed. These tools allow data analysts to represent multidimensional data in a 2D or 3D space, while preserving as much relevant information as possible. Yet, they cannot preserve all structures simultaneously and they induce some unavoidable distortions. Hence, many criteria have been introduced to evaluate a map's overall quality, mostly based on the preservation of neighbourhoods. Such global indicators are currently used to compare several maps, which helps to choose the most appropriate mapping method and its hyperparameters. However, those aggregated indicators tend to hide the local repartition of distortions. Thereby, they need to be supplemented by local evaluation to ensure correct interpretation of maps. In this paper, we describe a new method, called MING, for `Map Interpretation using Neighbourhood Graphs'. It offers a graphical interpretation of pairs of map quality indicators, as well as local evaluation of the distortions. This is done by displaying on the map the nearest neighbours graphs computed in the data space and in the embedding. Shared and unshared edges exhibit reliable and unreliable neighbourhood information conveyed by the mapping. By this mean, analysts may determine whether proximity (or remoteness) of points on the map faithfully represents similarity (or dissimilarity) of original data, within the meaning of a chosen map quality criteria. We apply this approach to two pairs of widespread indicators: precision/recall and trustworthiness/continuity, chosen for their wide use in the community, which will allow an easy handling by users.

**A. Gheeraert, L. Pacini, V.S Batista, L.Vuillon, C.Lesieur, I. Rivalta** Exploring Allosteric Pathways of a V-Type Enzyme with Dynamical Perturbation Networks
. *The Journal of Physical Chemistry B*,

Elucidation of the allosteric pathways in proteins is a computational challenge that strongly benefits from combination of atomistic molecular dynamics (MD) simulations and coarse-grained analysis of the complex dynamical network of chemical interactions based on graph theory. Here, we introduce and assess the performances of the dynamical perturbation network analysis of allosteric pathways in a prototypical V-type allosteric enzyme. Dynamical atomic contacts obtained from MD simulations are used to weight the allosteric protein graph, which involves an extended network of contacts perturbed by the effector binding in the allosteric site. The outcome showed good agreement with previously reported theoretical and experimental extended studies and it provided recognition of new potential allosteric spots that can be exploited in future mutagenesis experiments. Overall, the dynamical perturbation network analysis proved to be a powerful computational tool, complementary to other network-based approaches that can assist the full exploitation of allosteric phenomena for advances in protein engineering and rational drug design.

**E. Domenjoud, B. Laboureix, and L. Vuillon** Facet Connectedness of Arithmetic Discrete Hyperplanes with Non-Zero Shift
. *LNCS, International Conference on Discrete Geometry for Computer Imagery*,

We present a criterion for the arithmetic discrete hyperplane to be facet connected when θ is the connecting thickness. We encode the shift μ in a numeration system associated with the normal vector and we describe an incremental construction of the plane based on this encoding. We deduce a connectedness criterion and we show that when the Fully Subtractive algorithm applied to has a periodic behaviour, the encodings of shifts μ for which the plane is connected may be recognised by a finite state automaton.

**A. Frosini and L. Vuillon** Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses
. *Theoretical Computer Science*,

Among the very many research interests of Maurice Nivat, a special role, according to the produced literature, was played by the study of the algorithmic and combinatorial aspects of connected finite discrete sets of points called polyominoes. In particular, he addressed the problem of a faithful reconstruction of some subclasses of them by imposing convexity constraints. The present study fits in this research line, and relies on a well known algorithm that Maurice Nivat and co-authors defined 1996 for the reconstruction of hv-convex polyominoes by orthogonal projections in polynomial time. Here, we consider a hierarchy on this class of polyominoes, and we continue a longstanding research on the reconstruction of its first levels by specializing the above mentioned result. The algorithm we propose bases on the possibility of characterizing the elements of the second level of the hierarchy, by a logic formula belonging to Dual-Horn and so polynomially solvable. Some related open problems are also presented.

**R. Dorantes-Gilardi, L. Bourgeat, L. Pacini, L. Vuillon and C. Lesieur** In proteins, the structural responses of a position to mutation rely on the Goldilocks principle: not too many links, not too few
. *Physical Chemistry Chemical Physics*,
vol. 20,(39), (2018) 25399-25410.

A disease has distinct genetic and molecular hallmarks such as sequence variants that are likely to produce the alternative protein structures accountable for individual responses to drugs and disease development. Thus, to set up customized therapies, the structural influences of amino acids on one another need to be tracked down. Using network-based models and classical analysis of amino acid and atomic packing in protein structures, the influence of first shell neighbors on the structural fate of a position upon mutation, is revisited. Regardless of the type and position in a structure, amino acids satisfy on average over their neighbors, a low and similar number of atomic interactions, the average called the neighborhood watch (Nw). The structural tolerance of a position to mutation depends on the modulation of the composition and/or proximity of neighbors to maintain the same Nw, before and after mutation, at every position. Changes, upon mutation of the number of atomic interactions at the level of individual pairs (wij) are structurally tolerated but influence structural dynamics. Robust, fragile and rescue interactions can be identified with Nw and wij, offering a framework to classify sequence variants according to position-dependent structural changes.

**A.
Casagrande et L. Vuillon,** Sciences
humaines et sociales et méthodes du numérique, un mariage
heureux ?. *Les
Cahiers du numérique*,
vol. 13,(3), (2017) 115-136.

Un nouveau domaine de recherche a vu le jour récemment au travers d’un manifeste rédigé en 2010 : les humanités numériques. Ces dernières ont comme objectif de combiner les sciences humaines et sociales (SHS) avec les méthodes du numérique. Or, ce mariage semble difficile au premier abord car chaque discipline possède son propre univers sémantique ainsi que ses propres méthodologies : la communication n’est pas toujours évidente. Malgré ces difficultés, nous souhaitons montrer dans cet article que les méthodes du numérique en se mettant à l’écoute des problématiques des SHS peuvent apporter davantage de légitimité aux résultats des recherches en SHS. Nous présentons un exemple de recherche entre chercheurs en mathématiques-informatique et chercheurs en psychologie qui a consisté à réaliser un contrôle négatif sur une expérience sur le thème de la mémoire.

**C. Reutenauer
and L. Vuillon,** Palindromic
Closures and Thue-Morse Substitution for Markoff Numbers,
*Uniform
Distribution Theory *12
(2017), no. 2, 25-35.

We state a new formula to compute the Markoff numbers using iterated palindromic closure and the Thue-Morse substitution. The main theorem shows that for each Markoff number m, there exists a word v ∈ {a, b}∗ such that m − 2 is equal to the length of the iterated palindromic closure of the iterated antipalindromic closure of the word av. This construction gives a new recursive construction of the Markoff numbers by the lengths of the word s involved in the palindromic closure. This construction interpolates between the Fibonaccinumbers and the Pell numbers.

**L.
Vuillon, D. Dutykh and F. Fedele,** "Some
special solutions to the Hyperbolic NLS equation."
Communications
in Nonlinear Science and Numerical Simulation (2018).

The Hyperbolic Nonlinear Schrödinger equation (HypNLS) arises as a model for the dynamics of three-dimensional narrow-band deep water gravity waves. In this study, the symmetries and conservation laws of this equation are computed. The Petviashvili method is then exploited to numerically compute bi-periodic time-harmonic solutions of the HypNLS equation. In physical space they represent non-localized standing waves. Non-trivial spatial patterns are revealed and an attempt is made to describe them using symbolic dynamics and the language of substitutions. Finally, the dynamics of a slightly perturbed standing wave is numerically investigated by means a highly accurate Fourier solver.

**I.
Gambini and L. Vuillon, **Tiling
the space by polycube analogues to Fedorov’s polyhedra,
*Fundamenta
Informaticae*,
**146**,
(2) (2016), 197–209.

We investigate minimal polycubes in terms of volume that tile the R3 space like the Fedorov’s polyhedra. In fact the 5 Fedorov’s polyhedra are convex polyhedra that tile the space by translation and we construct geometrical discrete objects formed by union of cubes with the same number of faces than the Fedorov’s polyhedra.

**M.
Achoch, R. Dorantes-Gilardi, C. Wymant, G. Feverati, K. Salamatian,
L. Vuillon and C. Lesieur,** Protein
structural robustness to mutations : an in silico investigation,
*Physical
Chemistry Chemical Physics*,
(2016).

Proteins possess qualities of robustness and adaptability to perturbations such as mutations, but occasionally fail to withstand them, resulting in loss of function. Herein, the structural impact of mutations is investigated independently of the functional impact. Primarily, we aim at understanding the mechanisms of structural robustness pre-requisite for functional integrity. The structural changes due to mutations propagate from the site of mutation to residues much more distant than typical scales of chemical interactions, following a cascade mechanism. This can trigger dramatic changes or subtle ones, consistent with a loss of function and disease or the emergence of new functions. Robustness is enhanced by changes producing alternative structures, in good agreement with the view that proteins are dynamic objects fulfilling their functions from a set of conformations. This result, robust alternative structures, is also coherent with epistasis or rescue mutations, or more generally, with non-additive mutational effects and compensatory mutations. To achieve this study, we developed the first algorithm, referred to as Amino Acid Rank (AAR), which follows the structural changes associated with mutations from the site of the mutation to the entire protein structure and quantifies the changes so that mutations can be ranked accordingly. Assessing the paths of changes opens the possibility of assuming secondary mutations for compensatory mechanisms.

**A.
Casagrande, E. Loza-Aguirre and L. Vuillon,**
*Improving
strategic scanning information analysis : an optimized measure for
information proximity evaluation*.
In Third International Conference on Entreprise Systems (IEEE
conference). Bale. 2015.

Strategic Scanning activities become less effective when faced with managing information overload. This paper introduces “nearness measure” (NM), a measure for information proximity evaluation. We also present and analyze the principles and properties of a graphical representation of the measure. We compare the measure to the usual Cosine similarity (CS). Even when the algorithm that calculates NM between texts is larger than CS in terms of complexity, NM with a minimization phase expresses an analysis of the documents from the general to the specific that is the opposite to what CS does. Thus, the manager using NM would require less time to explore collected information.

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

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.

F. De Carli, A. Frosini, S. Rinaldi and L. Vuillon ``How to construct convex polyominoes on DNA Wang tiles ? '' LAMA research report

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. **

G. Paquin and L. Vuillon ``A characterization of balanced episturmian sequences'' Electronic Journal of Combinatorics. Volume 14 (2007)

**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). **

S. Brlek, S. Dulucq, A. Ladouceur and L. Vuillon ``Combinatorial properties of smooth infinite words'' Theoretical Computer Science,

**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'' Pure Mathematics and Applications, Volume 18 (2007), Issue No. 3-4

**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. **