Palindromic Ziv–Lempel and Crochemore Factorizations of m-Bonacci Infinite Words ; ; et al in Theoretical Computer Science (in press) We introduce a variation of the Ziv–Lempel and Crochemore factorizations of words by requiring each factor to be a palindrome. We compute these factorizations for the Fibonacci word, and more generally ... [more ▼] We introduce a variation of the Ziv–Lempel and Crochemore factorizations of words by requiring each factor to be a palindrome. We compute these factorizations for the Fibonacci word, and more generally, for all m-bonacci words. [less ▲] Detailed reference viewed: 18 (2 ULiège)Cobham’s Theorem and Automaticity ; ; et al in International Journal of Foundations of Computer Science (in press) We make certain bounds in Krebs’ proof of Cobham’s theorem explicit and obtain corresponding upper bounds on the length of a common prefix of an aperiodic a-automatic sequence and an aperiodic b-automatic ... [more ▼] We make certain bounds in Krebs’ proof of Cobham’s theorem explicit and obtain corresponding upper bounds on the length of a common prefix of an aperiodic a-automatic sequence and an aperiodic b-automatic sequence, where a and b are multiplicatively independent. We also show that an automatic sequence cannot have arbitrarily large factors in common with a Sturmian sequence. [less ▲] Detailed reference viewed: 20 (4 ULiège)Extensions of the Pascal Triangle to Words, and Related Counting Problems Stipulanti, Manon Doctoral thesis (2019) The Pascal triangle and the corresponding Sierpiński fractal are fairly well-studied mathematical objects, which both exhibit connections with many different scientific areas. The first is made of ... [more ▼] The Pascal triangle and the corresponding Sierpiński fractal are fairly well-studied mathematical objects, which both exhibit connections with many different scientific areas. The first is made of binomial coefficients of integers that notably appear in combinatorics to tackle counting problems (for instance, they provide the number of possible ways to choose a given amount of elements from a set of elements). There exist multiple generalizations of those binomial coefficients. In this text, we focus on binomial coefficients of words, which count scattered subwords. The red thread of this thesis is precisely the combination of the Pascal triangle and binomial coefficients of words. The first part is dedicated to extensions of the Pascal triangle to various sets of words (languages) associated with different numeration systems. We transport the existing link between the Pascal triangle and the Sierpiński gasket to this wider setting. The second part is concerned with particular sequences extracted from generalized Pascal triangles. They count non-zeroes binomial coefficients on each row of a given Pascal-like triangle. We study their regularity and their automaticity with respect to different numeration systems. In the third and last part, we establish the asymptotics of the summatory functions of the sequences considered previously. The most important feature of this part might not necessarily be the result itself, but the underlying new method to achieve it. [less ▲] Detailed reference viewed: 45 (17 ULiège)The formal inverse of the period-doubling word Stipulanti, Manon Conference (2019, March 12) We deal with formal inverse (in terms of formal series) of the period-doubling sequence. The sequence of indices at which the period-doubling sequence takes the value 0 (resp., 1) is shown to be not k ... [more ▼] We deal with formal inverse (in terms of formal series) of the period-doubling sequence. The sequence of indices at which the period-doubling sequence takes the value 0 (resp., 1) is shown to be not k-regular for any k>1. We give recurrence relations for its formal inverse, then we show that it is 2-automatic, and we also provide an automaton that generates it. We study the sequence of indices at which this formal inverse takes the value 1, and we show that it is not k-regular for any k>1 by connecting it to the characteristic sequence of Fibonacci numbers. [less ▲] Detailed reference viewed: 22 (2 ULiège)Nyldon words Charlier, Emilie ; ; Stipulanti, Manon in Journal of Combinatorial Theory. Series A (2019), 167 The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define ... [more ▼] The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define the family of Lyndon words in a recursive way. If the lexicographic order is reversed in this definition, we obtain a new family of words, which are called the Nyldon words. In this paper, we show that every finite word can be uniquely factorized into a lexicographically nondecreasing sequence of Nyldon words. Otherwise stated, Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. Then we investigate this new family of words. In particular, we show that Nyldon words form a right Lazard set. [less ▲] Detailed reference viewed: 27 (12 ULiège)Convergence of Pascal-Like Triangles in Parry–Bertrand Numeration Systems Stipulanti, Manon in Theoretical Computer Science (2019), 758 We pursue the investigation of generalizations of the Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of ... [more ▼] We pursue the investigation of generalizations of the Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. The finite words occurring in this paper belong to the language of a Parry numeration system satisfying the Bertrand property, i.e., we can add or remove trailing zeroes to valid representations. It is a folklore fact that the Sierpiński gasket is the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from the classical Pascal triangle modulo 2. In a similar way, we describe and study the subset of [0, 1] × [0, 1] associated with the latter generalization of the Pascal triangle modulo a prime number. [less ▲] Detailed reference viewed: 49 (9 ULiège)A way to extend the Pascal triangle to words Stipulanti, Manon Conference (2018, November 16) The Pascal triangle and the corresponding Sierpinski gasket are well-studied objects. They exhibit self-similarity features and have connections with dynamical systems, cellular automata, number theory ... [more ▼] The Pascal triangle and the corresponding Sierpinski gasket are well-studied objects. They exhibit self-similarity features and have connections with dynamical systems, cellular automata, number theory and automatic sequences in combinatorics on words. In this talk, I will first recall the well-known link between those two objects. Then I will exploit it to define Pascal-like triangles associated with different numeration systems, and their analogues of the Sierpinski gasket. This a work in collaboration with Julien Leroy and Michel Rigo (University of Liège, Belgium). [less ▲] Detailed reference viewed: 42 (5 ULiège)A way of extending Pascal and Sierpinski triangles to finite words Stipulanti, Manon Conference (2018, September 24) Combinatorics on words is a relatively new domain of discrete mathematics, which focuses on the study of words and formal languages. In this context, a finite word is simply a finite sequence of letters ... [more ▼] Combinatorics on words is a relatively new domain of discrete mathematics, which focuses on the study of words and formal languages. In this context, a finite word is simply a finite sequence of letters, or symbols, that belong to a finite set called the alphabet. For instance, 01101 and 01 are two finite (binary) words over the binary alphabet {0, 1}. The binomial coefficient (u,v) of two finite words u and v is the number of occurrences of v as a v subsequence of u. For example, (01101,01) = 4. This concept, which is a natural generalization of the classical binomial coefficients of nonnegative integers, has been widely studied for the last thirty years or so. In this talk, I will first recall the link between the classical Pascal triangle and the Sierpiński gasket, and then present a way of extending both objects to binomial coefficients of (binary) words. [less ▲] Detailed reference viewed: 27 (2 ULiège)Some generalizations of the Pascal triangle: base 2 and beyond Stipulanti, Manon Conference (2018, April 27) The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance ... [more ▼] The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance, (abbabab,ab)=4. This concept naturally extends the classical binomial coefficients of integers, and has been widely studied for about thirty years (see, for instance, Simon and Sakarovitch). In this talk, I present the research lead from October 2015: I give the main ideas that lead to an extension of the Pascal triangles to base-2 expansions of integers. After that, I extend the work to any Parry-Bertrand numeration system including the Fibonacci numeration system. [less ▲] Detailed reference viewed: 27 (5 ULiège)Pascal-like triangles: base 2 and beyond Stipulanti, Manon Conference (2018, March 16) The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance ... [more ▼] The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance, (abbabab,ab)=4. This concept naturally extends the classical binomial coefficients of integers, and has been widely studied for about thirty years (see, for instance, Simon and Sakarovitch). In this talk, I present the research lead since October 2015: I give the main ideas that give an extension of the Pascal triangle to base-2 expansions of integers and also give an overview of the results obtained so far, linked to this generalization. In the last part of this presentation, I extend the results to the Fibonacci setting. [less ▲] Detailed reference viewed: 25 (3 ULiège)The Formal Inverse of the Period-Doubling Sequence ; Stipulanti, Manon in Journal of Integer Sequences (2018), 21(9), 189122 If $p$ is a prime number, consider a p-automatic sequence $(u_n)_{n\ge 0}$, and let $U(X) = $\sum_{n\ge 0} u_nX^n ∈ F_p[[X]]$ be its generating function. Assume that there exists a formal power series $V ... [more ▼] If $p$ is a prime number, consider a p-automatic sequence $(u_n)_{n\ge 0}$, and let $U(X) = $\sum_{n\ge 0} u_nX^n ∈ F_p[[X]]$ be its generating function. Assume that there exists a formal power series $V(X) = \sum_{n\ge 0} v_n X^n ∈ F_p[[X]]$ which is the compositional inverse of $U$, i.e., $U(V(X)) = X = V(U(X))$. The problem investigated in this paper is to study the properties of the sequence $(v_n)_{n\ge 0}$. The work was first initiated for the Thue–Morse sequence, and more recently the case of other sequences (variations of the Baum-Sweet sequence, variations of the Rudin-Shapiro sequence and generalized Thue-Morse sequences) has been treated. In this paper, we deal with the case of the period-doubling sequence. We first show that the sequence of indices at which the period-doubling sequence takes the value 0 (resp., 1) is not k-regular for any $k \ge 2$. Secondly, we give recurrence relations for its formal inverse, then we show that it is 2-automatic, and we also provide an automaton that generates it. Thirdly, we study the sequence of indices at which this formal inverse takes the value 1, and we show that it is not k-regular for any $k \ge 2$ by connecting it to the characteristic sequence of Fibonacci numbers. We leave as an open problem the case of the sequence of indices at which this formal inverse takes the value 0. [less ▲] Detailed reference viewed: 38 (4 ULiège)Counting Subwords Occurrences in Base-b Expansions Leroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Integers: Electronic Journal of Combinatorial Number Theory (2018), 18A We consider the sequence (Sb(n))n≥0 counting the number of distinct (scattered) subwords occurring in the base-b expansion of the non-negative integers. By using a convenient tree structure, we provide ... [more ▼] We consider the sequence (Sb(n))n≥0 counting the number of distinct (scattered) subwords occurring in the base-b expansion of the non-negative integers. By using a convenient tree structure, we provide recurrence relations for (Sb(n))n≥0 leading to the b-regularity of the latter sequence. Then we deduce the asymptotics of the summatory function of the sequence (Sb(n))n≥0. [less ▲] Detailed reference viewed: 68 (22 ULiège)An extension of the Pascal triangle and the Sierpiński gasket to finite words Stipulanti, Manon Conference (2017, December 15) The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance ... [more ▼] The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance, (abbabab,ab)=4. This concept naturally extends the classical binomial coefficients of integers, and has been widely studied for about thirty years (see, for instance, Simon and Sakarovitch). In this talk, I present the research lead from October 2015: I give the main ideas that lead to an extension of the Pascal triangles to base-2 expansions of integers and also give an overview of the results obtained so far, linked to this generalization. [less ▲] Detailed reference viewed: 29 (4 ULiège)Pascal triangles and Sierpiński gasket extended to binomial coefficients of words Stipulanti, Manon Conference (2017, November 29) The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance, (abbabab,ab)=4. This concept naturally extends the classical binomial coefficients of integers, and has been widely studied for about thirty years (see, for instance, Simon and Sakarovitch). In this talk, I present the research lead from October 2015 on an extension of the Pascal triangles to base-2 expansions of integers. In a first part, I define two new objects that both generalize the classical Pascal triangle and the Sierpinski gasket. In a second part, I define a new sequence extracted from the Pascal triangle in base 2 and study its regularity. In a third part, I exhibit an exact formula for the behavior of the summatory function of the latter sequence. [less ▲] Detailed reference viewed: 26 (2 ULiège)Generalized Pascal triangles for binomial coefficients of finite words Stipulanti, Manon Conference (2017, June 19) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. Then we create a new sequence from this extended Pascal triangle that counts, on each row of this triangle, the number of positive binomial coefficients. We show that this sequence is 2-regular. To extend our work, we construct a Pascal triangle using the Fibonacci representations of all the nonnegative integers and we define the corresponding sequence of which we study the regularity. This regularity is an extension of the classical k-regularity of sequences. [less ▲] Detailed reference viewed: 60 (10 ULiège)Generalized Pascal triangles for binomial coefficients of finite words Stipulanti, Manon Conference (2017, June 16) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. Then we create a new sequence from this extended Pascal triangle that counts, on each row of this triangle, the number of positive binomial coefficients. We show that this sequence is 2-regular. To extend our work, we construct a Pascal triangle using the Fibonacci representations of all the nonnegative integers and we define the corresponding sequence of which we study the regularity. This regularity is an extension of the classical k-regularity of sequences. [less ▲] Detailed reference viewed: 46 (8 ULiège)Triangles de Pascal et compagnie Stipulanti, Manon Conference (2017, April 19) Le triangle de Pascal classique ainsi que le triangle de Sierpiński sont des objets largement étudiés. Ils montrent des aspects auto-similaires et ont des liens avec les systèmes dynamiques, les automates ... [more ▼] Le triangle de Pascal classique ainsi que le triangle de Sierpiński sont des objets largement étudiés. Ils montrent des aspects auto-similaires et ont des liens avec les systèmes dynamiques, les automates cellulaires, la théorie des nombres et les suites dites automatiques. Dans ce séminaire, nous présentons un travail en collaboration avec Julien Leroy et Michel Rigo. Dans un premier temps, nous introduisons une généralisation du triangle de Pascal basée sur les coefficients binomiaux de mots finis et nous étudions le cas plus particulier des représentations en base 2. Ces coefficients comptent le nombre de fois qu’un mot fini apparaît comme sous-suite d’un autre mot fini. De la même façon que le triangle de Sierpiński peut être construit comme l’ensemble limite, pour la distance de Hausdorff, d’une suite convergente de compacts renormalisés extraits du triangle de Pascal classique modulo 2, nous décrivons et étudions les premières propriétés du sous-ensemble de [0, 1] × [0, 1] associé à ce triangle de Pascal généralisé modulo un nombre premier p. Dans un second temps, nous étudions la suite qui compte, sur chaque ligne du triangle de Pascal généralisé en base 2, le nombre de coefficients binomiaux strictement positifs. Cette suite présente une régularité étonnante qui peut être mise en évidence en utilisant une structure particulière de graphes, appelée arbre des sous-mots. [less ▲] Detailed reference viewed: 75 (14 ULiège)Behavior of digital sequences through exotic numeration systems Leroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Electronic Journal of Combinatorics (2017), 24(1), 14436 Many digital functions studied in the literature, e.g., the summatory function of the base-k sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied ... [more ▼] Many digital functions studied in the literature, e.g., the summatory function of the base-k sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied using techniques from analytic number theory or linear algebra. In this paper we develop a method based on exotic numeration systems and we apply it on two examples motivated by the study of generalized Pascal triangles and binomial coefficients of words. [less ▲] Detailed reference viewed: 106 (29 ULiège)Des triangles de Pascal généralisés aux coefficients binomiaux de mots finis Stipulanti, Manon Conference (2017, January 23) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we show the existence of a subset of [0, 1]×[0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 53 (6 ULiège)Generalized Pascal triangles for binomial coefficients of words: a short introduction Stipulanti, Manon Conference (2017, January 09) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 59 (8 ULiège) |
||