Dr Lama Tarsissi

Research Interests

• My research focuses on theoretical computer science issues, at the intersection of graph theory, computational geometry (mainly in the discrete domain) and computational complexity theory. One of the major axis is that of formal languages, in particular that of the Combinatorics of words
• My research works are based on Christoffel's words and their applications, which allowed me to work on three different axes and with different techniques. I also extended and applied the results of my research to the problem of digital convexity

1. Second order of balance for Christoffel words:

Finding balanced words was the goal of several mathematicians like Altman, Hubert and Tijdeman. Note that a binary word is balanced if for two factors of the same length, the number of occurrences of a letter in the two words is either the same or of a difference that does not exceed 1. This area has been studied extensively in recent years. We can notice that balance is a notion that we can find in our daily life. Indeed, the majority of this theory is implicitly developed to be a tool allowing to solve several problems in computing, in particular the questions of synchronisation of processes or words. Christoffel's words are considered the most interesting among the balanced finite word families. These words are fundamental objects in combinatorics and admit geometric, algebraic and arithmetic properties. In discrete geometry, Christoffel words are the encoding of a discrete segment on a grid of (0,0) up to (a, b). Christoffel words have an algebraic interpretation using Cayley's graph and two generators g1 = a and g2 = b over Z / nZ with n = a + b. The study of these words began in 1875 with Elwin Christoffel and his collaborators. One can find several works of Elwin Christoffel and Reutenauer which give all the characteristics of this family of words.

Christoffel's words are 1-balanced or simply balanced words. We will use the basic notations where |w| represents the length of the word w, and we have that the word w is k-balanced if, for all two factors of the same length u, v of w, and for any letter of the alphabet A:

| u | = | v | ---> || u | _a - | v | _a | <= k.

To study the equilibrium order of these words in an explicit way, I introduced a matrix Bw of dimension (n-1) X n where w represents the finite-length binary word n, which gives the equilibrium order of this word. The maximum value of this matrix is the equilibrium order dw of the binary word used. Each entry Bw [i, j] gives the normalised value of the number of occurrences of a certain letter, of the alphabet, of the factor which is of length i and at the position j with respect to w.

The matrix Bw is obtained thanks to a construction that I proposed, by a recursive algorithm which is deduced from the study of the equilibrium of the word w. From this matrix, we can extract several properties and relations that help us better understand the construction of these binary words. We can notice that as the Christoffel words are balanced words then each line of Bw will be formed by a binary word. In order to better understand the equilibrium and the notion of dispersion of these letters in Christoffel's word, I repeated the equilibrium test on each row of this matrix while building a new matrix which I called the matrix of second order equilibrium, and denoted by Uw. This matrix gives a second order of equilibrium d2 w , corresponding to the maximum value of the matrix. Each input of Uw is obtained by calculating: Uw [i, j] = max (Bbw[i] [j]).

There is an isomorphism between the tree of Christoffel, which is the tree which contains all the words of Christoffel with rational slope, and the tree of Stern-Brocot, which is the tree which contains all the rational numbers a/b where a and b are relatively prime. Using this isomorphism, arithmetic techniques and the properties of continuous fractions, I have been able to demonstrate that it is possible to decompose Uw into 9 blocks, and thanks to the existing symmetries, it is sufficient to know 3 blocks among these 9. Additionally, I was able to obtain the Uw matrix recursively, based on parts of the matrices of some fractions at lower levels in the Stern-Brocot tree.

Throughout the Stern-Brocot tree, and looking at the paths that minimise the value of d2, I noticed that the path followed by the fractions obtained from the ratio of consecutive numbers of the Fibonacci sequence, called the Zig- zag path, is one of the minimum paths. As the Zig-Zag path is not the unique path, I found the form of rationals in continued fractions which determines these minimum paths.

2. Synchronisation of Christoffel words

The initial objective of my thesis was to approach and attack the Fraenkel conjecture which has been open for over 40 years. It consists in proving the existence and the uniqueness of the equilibrated words (up to a permutation) on k letters with frequencies which are two-by-two distinct and of the form: 2k/2k+1 -1 . . . .2/2k+1 -1, 1/2k+1-1. This conjecture has been proved true for 1 <= k <= 7 by different methods and different authors, such as Fraenkel himself, Morikawa, Graham , Altman, Gaujal, Hordijk and Tijdeman. The evidence was based on Beatty's sequels, exact family cover and the words équilibrés. Christoffel's words are also found in the study of the synchronsation of k processes using k balanced words. For k = 2, we fall back on Christoffel's words, while for k> 2, the situation is more complicated and leads us to the Fraenkel conjecture. This conjecture being difficult to prove, we have thought to build tools that help us approach it. We therefore thought of studying the synchronisation of palindromes, which are words read in exactly the same way in both directions, while taking into account the fact that Christoffel's words are factored into the product of two palindromes. So, I studied the synchronisation of these words which have several characteristics. Paquin and Reuteneuar have introduced a technique which allows to give the synchronisation matrix of two Christoffels. The first column of this matrix is called "seed" and it is made up of two rows which contain the correct first values of the Cayley graph of each Christoffel word used. Using the concept of the seed, I have given the seed shape useful for Christoffel's three word synchronisation. Several cases have been studied according to the parity of n where n represents the sum of the generators. In addition, I was able to determine the general seed shape of any number of generators having the form 2i.

3. Discrete Tomography

Another line of work is that of discrete tomography, which addresses the problem of reconstructing binary images from a small number of their projections. I focused on the reconstruction of polyominoes and digital convex sets, within the framework of discrete two-dimensional geometry. I was able to use my knowledge of Christoffel's words to advance on the problem of reconstruction of digital convex polyominoes. A polyomino is the discrete analogue of the interior of a Jordan curve. A polyomino is a finite subset of Z2 such that its complement and itself are both 4-related. Using Freeman's code, we can consider the polyomino as a finite set of pixels and we can encode its edge on a four-letter alphabet. The latter is reduced to two letters each time we consider one of the 4 quadrants of the polyomino, when placed in a rectangle. Several geometric properties of the polyomino translate into a combinatorial property of its contour word. Discrete convexity was studied at the end of the sixties with Minsky and Papert. We can see that the contour of a polyomino is based on concepts from combinatorics on words. More clearly, a convex form is obtained if and only if the unique factorisation of the word contour into decreasing Lyndon words is formed only of Christoffel. In other words, a shape is digital convex if and only if the word contour is formed from Christoffel's words with increasing slopes. Note that Lyndon's words are the smallest words among all of their conjugates, where the order used here is lexicographic order.

4. Preservation of discrete convexity during a transformation

The topic of the study is the displacement on regular tiling of space in dimension two or three, an important question which has applications in imagery. This theme is based on digitisation, defined as a rounding function, D: Rn > Zn. An image is represented mathematically by a function defined on a domain of Rn, n = 2, 3. In order to store, process and manipulate such an image by computer, it is digitised by partitioning the support Rn by polygons. The rotations of its images are notably involved in the recognition of shapes in digital images in two and three dimensions. For this, the transformations T: Rn > Rn are digitised by setting TD: = D°T | Zn. If in Rn, the geometry and topology are preserved by the transformations T, on the other hand in the discrete domain, that is to say on Zn and no longer Rn, this geometric and topological invariant is often lost, in particular because of the discontinuities induced by the digitisation process of the function TD: Zn ------> Zn.

5. 3-Uniform Hypergraph

Recently, I have been interested in the characterisation and reconstruction of 3-uniform hypergraph from their power suite. Effective characterisations have been proposed by Erdôs and Gallai for simple graphs (graphs that do not contain a loop or a parallel stop). For hypergraphs, my colleagues and I have demonstrated that a similar characterisation is not possible, even in the simplest cases of 3-uniform hypergraphs. In addition, we have shown that the "null-labeling" problem of 3-uniform hypergraphs is an NP-complete problem.

PhD in

• Mathematics and Computer Sciences

Research Collaborations Conferences

• 2021: Journées de géometrie Discrète et Morphologie mathématique-Nancy-France
• 2019: The 5th Asian Conference on Pattern Recognition (ACPR) - Auckland-New Zealand (Poster)
• 2019: Mathemetic aspects of computer and information sciences(MACIS) – Istanbul-Turkie
• 2019: Journée GT-GDMM – Marseille-France
• 2019: Meeting on Tomography and Applications Discrete Tomography and Image Reconstruction -Milan-Italie
• 2018: Journées Montoises - Bordeaux-FranceX2018Journée MDSC – Nice-France
• 2018: Meeting on Tomography and Applications Discrete Tomography and Image Reconstruction -Milan-Italie
• 2017: Words 2017 - Montréal-CanadaX2017Meeting on Tomography and Applications Discrete Tomography and Image Reconstruction -Milan-Italie
• 2016: Journées Montoises – Liège-Belgique
• 2016: 3rd Algorithmic and Enumerative Combinatorics – Hagenberg-Autriche (Poster)
• 2015: Interaction – Grenoble-France

Seminaires

• 2019: Seminaire à l’ Université de Firenze – Florence-Italie
• 2019: Seminaire à l’Université de Liège – Liège-Belgique
• 2019: Seminaire à LIRIF, Paris diderot – Paris-France
• 2018: Seminaire au LIGM, Paris Marne-la-vallée – Paris-France
• 2018: Seminaire à l’Université de Firenze – Florence-Italie
• 2018: Seminaire au Laboratoire I3S - Sophia Antipolis-France
• 2017: Seminaire au Laboratoire LAMA, équipe LIMD – Chambéry-France
• 2016: Seminaire au Laboratoire LAMA. - Chambéry-France
• 2015: Seminaire des doctorants au Laboratoire LAMA – Chambéry-France

Publications Book Chapters

• Ascolese, M., Frosini, A., Kocay, W.L., Tarsissi, L.-2021. "Properties of unique degree sequences of 3-uniform hypergraphs" -Discrete Geometry and Mathematical Morphology (DGMM)}- Upsala- Sweeden
• Frosini, A., Tarsissi, L. - 2020. The characterisation of the minimal paths in the Christoffel tree according to a second-order balancedness. Development in Language Theory (DLT) - Tampa, USA. (hal-02495529) (LNCS, volume 12086) - URL
• Tarsissi, L., Coeujolly, D., Kenmochi, Y., Romon, P. - 2019. Convexity Preserving Contraction of Digital Sets. Asian Conference on Pattern Recognition (ACPR) - Auckland, New-Zealand. (hal-02315084) (LNCS, volume 12047) -URL
• Tarsissi, L., Vuillon, L. 2019. Second order balance property on Christoffel words. Mathematical Aspects of Computer and Information Sciences (MACIS) - Istanbul-Turkey. (hal-02433984) (LNCS, volume 11989)- URL
• Dulio, P., Frosini, A. Rinaldi, S. Tarsissi, L., Vuillon, L. 2017. First Steps in the Algorithmic Reconstruction of Digital Convex Sets. WORDS - Montréal-Canada. (LNCS volume 10432) -URL
• Borel, J-P., Tarsissi, L., Vuillon, L. 2018. Inflation of Digital Convex Polyominoes. Journ\'ees montoises d'informatique th\'eorique - Bordeaux-France. (hal-02042696) URL

Journal Articles

• Dulio, P., Frosini, A. Rinaldi, S. Tarsissi, L., Vuillon, L. 2021. "Further steps on the reconstruction of convex polyominoes from orthogonal projections". Journal of Combinatorial Optimisation-URL
• Frosini, A., Kocay, W., Palma, G., Tarsissi, L.. 2020. "On Null 3-Hypergraphs". Discrete Applied Mathematics - URL

Affiliations

• Sorbonne University Abu Dhabi-UAE
• ESIEE-Université Paris Est Marne la vallée-France
• LIGM-Université Paris Est Marne la vallée-France
• Sophia Antipolis-Université de Nice- France
• Université Savoie Mont blanc-Bourget du lac- France