K. Medková, E. Pelantová, L. Vuillon Derived sequences of complementary symmetric Rote sequences . RAIRO-Theoretical Informatics and Applications.

Complementary symmetric Rote sequences are binary sequences which have factor com- plexity C(n) = 2n for all integers n ≥ 1 and whose languages are closed under the exchange of letters. These sequences are intimately linked to Sturmian sequences. Using this connection we investigate the return words and the derivated sequences to the prefixes of any complementary symmetric Rote sequence v which is associated with a standard Sturmian sequence u. We show that any non-empty prefix of v has three return words. We prove that any derivated sequence of v is coding of three interval exchange transformation and we determine the parameters of this transformation. We also prove that v is primi- tive substitutive if and only if u is primitive substitutive. Moreover, if the sequence u is a fixed point of a primitive morphism, then all derivated sequences of v are also fixed by primitive morphisms. In that case we provide an algorithm for finding these fixing morphisms.

L. Pacini, L. Vuillon, C. Lesieur Induced Perturbation Network and tiling for modeling the L55P Transthyretin amyloid fiber. . Procedia Computer Science 178, 8-17.

Protein structures are complex spatial systems, formed by the three-dimensional arrangement of amino acids, that interact through atomic contacts. It is fundamental to understand the perturbation mechanisms associated with the amino acid mutations that lead to changes in a protein dynamics, as such mutations can lead to diseases. We present a methodology based on Amino Acid Networks and the use of Induced Perturbation Networks to infer the impact of amino acid mutations on a protein’s dynamics and the use of a tiling formalism to model protein aggregation. We apply this methodology to the case study of the L55P Transthyretin (TTR) variant, one of the most pathogenic mutations of TTR, due to its increased tendency to aggregate into amyloid fibers. We show that another pathogenic variant, V30M TTR, produces different results, reflecting a different pathogenic mechanism compared to that another pathogenic variant, V30M TTR, produces different results, reflecting a different pathogenic mechanism compared to L55P TTR and that the results differ for pathogenic and non-pathogenic variants (L55P and V30M TTR pathogenic variants versus L55P TTR and that the results differ for pathogenic and non-pathogenic variants (L55P and V30M TTR pathogenic variants versus T119Y and T119M non-pathogenic variants).

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 123 (16), 3452-3461, 2019,

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 777, 329-337, 2019,

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 '' Theoretical Computer Science 624 (2016) 101–108.

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 infinite 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 finite 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 configurations 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.

F. De Carli, A. Frosini, S. Rinaldi and L. Vuillon ``On the tiling system recognizability of various classes of convex polyominoes''  Annals of Combinatorics, Volume 13, issue 2 (2009)

We consider some problems concerning two relevant classes of two-dimensional languages, i.e. the tiling recognizable languages, and the local languages, recently introduced by Giammarresi and Restivo, and already extensively studied. We show that various classes of convex and column-convex polyominoes can be naturally represented as two-dimensional words of tiling recognizable languages. Moreover we investigate the nature of the generating function of a tiling recognizable language, providing evidence that such a generating function needs not be D-finite.

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.

In this article we consider the class of pseudo-square polyominoes, introduced by Beauquier and Nivat for tiling the plane, and the subclass PSP of pseudo-square parallelogram polyominoes. In particular we provide by means of a rational language the enumeration of the subclass of psp-polyominoes with a fixed planar basis according to the semi-perimeter. The case of pseudo-square convex polyominoes is also analyzed.

L. Vuillon Editor of the Special Issue of TCS on ``Combinatorics of the Discrete Plane and Tilings''

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, Volume 352, issue 1-3 pages 306-317 (2006).

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,Volume 347, Issues 1-2, 30 November 2005, Pages 370-392.

 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 Volume 346, Issues 2-3, 28 November 2005, Pages 226-253.

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 :

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

Thèse :

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

``Contribution à l'étude des pavages et des surfaces discrétisées''

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