Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Mathémagie - L'art de la divination Vandomme, Elise Speech/Talk (2016) Cet exposé est basé sur la suite des exposés Mathémagie (I, II, III) de Michel Rigo. Nous présentons ici 10 tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien ... [more ▼] Cet exposé est basé sur la suite des exposés Mathémagie (I, II, III) de Michel Rigo. Nous présentons ici 10 tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien : des tours de cartes, des tours de divination et le célèbre tour du ``barman aveugle avec des gants de boxe''. Contrairement au magicien qui ne dévoile jamais ses secrets, ici, nous expliquons que ces tours reposent sur diverses propriétés et constructions mathématiques, comme la théorie des graphes ou la combinatoire des mots. [less ▲] Detailed reference viewed: 20 (1 ULg)Identifying codes in vertex-transitive graphs and strongly regular graphs ; ; et al in Electronic Journal of Combinatorics (2015), 22(4), 46 We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2ln(|V|)+1 where V ... [more ▼] We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2ln(|V|)+1 where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order |V|^α with α∈{14,13,25}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs. [less ▲] Detailed reference viewed: 36 (10 ULg)Use of the wavelet theory as a tool to investigate the l-abelian complexity of a sequence Kleyntssens, Thomas ; Nicolay, Samuel ; Vandomme, Elise et al Poster (2015, September 23) The concept of k-automatic sequences is at the intersection of number theory and formal language theory. It has been generalized by the notion of k-regularity that allows to study sequences with values in ... [more ▼] The concept of k-automatic sequences is at the intersection of number theory and formal language theory. It has been generalized by the notion of k-regularity that allows to study sequences with values in a (possibly infinite) ring. This concept provides us with structural information about how the different terms of the sequence are related to each other. They are many different notions related to the measure of complexity of an infinite sequence w. A classical approach is its factor complexity. In an abelian context, the analogue to the factor complexity is the abelian complexity where the number of distinct factors of length n is counted up to abelian equivalence. The notion of abelian complexity was extended to that of l-abelian complexity. In this talk, I propose to use tools from the wavelet theory to analyze the l-abelian complexity. For the numerical simulations, I apply the wavelet leaders method that allows to study the pointwise regularity of signals. [less ▲] Detailed reference viewed: 17 (5 ULg)Contributions to combinatorics on words in an abelian context and covering problems in graphs Vandomme, Elise Doctoral thesis (2015) This thesis dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an ... [more ▼] This thesis dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue--Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^a with a in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich. [less ▲] Detailed reference viewed: 166 (45 ULg)A New Approach to the 2-Regularity of the ℓ-Abelian Complexity of 2-Automatic Sequences ; Rigo, Michel ; Rowland, Eric et al in The Electronic Journal of Combinatorics (2015), 22(1), 127 We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem ... [more ▼] We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem to develop a general approach for studying the l-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue--Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. [less ▲] Detailed reference viewed: 44 (14 ULg)A new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences (extended abstract) ; Rigo, Michel ; Rowland, Eric et al Conference (2014, September) We show that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit. We apply this theorem to develop a general approach for studying the ℓ-abelian complexity ... [more ▼] We show that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit. We apply this theorem to develop a general approach for studying the ℓ-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue–Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. [less ▲] Detailed reference viewed: 18 (5 ULg)Identifying codes in vertex-transitive graphs ; Parreau, Aline ; et al Conference (2014, July) We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) where V is the ... [more ▼] We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order |V|^a with a in {1/4, 1/3, 2/5}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs. [less ▲] Detailed reference viewed: 23 (7 ULg)A conjecture on the 2-abelian complexity of the Thue-Morse word Rigo, Michel ; Parreau, Aline ; Vandomme, Elise Conference (2014, January 20) The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k ... [more ▼] The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k-abelian complexity is a generalization of the abelian complexity, corresponding to the case where k=1. Formally, two words u and v of the same length are k-abelian equivalent if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The aim of this talk is to study the 2-abelian complexity a(n) of the Thue-Morse word. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a work of Madill and Rampersad (2012) where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will present some arguments supporting our conjecture. They are based on functions counting some subword of length 2 occuring in prefixes of the Thue-Morse word. [less ▲] Detailed reference viewed: 56 (18 ULg)Linear formulation of identifying cdes in graphs Vandomme, Elise ; ; Parreau, Aline Poster (2013, September 09) Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The ... [more ▼] Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The placement of sensors in the rooms corresponds to choosing a subset of vertices. Finding a sensor-placement such that the location of a fire in one room can be precisely determined is equivalent to constructing an identifying code in the graph. These are dominating sets of vertices for which the closed neighbourhood of each vertex (i.e., the vertex and its neighbours) has a unique intersection with the set. The problem of finding an identifying code has been widely studied. Yet its formulation as an integer linear problem hasn't been much considered. Let G be a graph with vertex set V, to an identifying code $C\subseteq V$ of $G$ correspond weights x_u (x_u is 1 if u belongs to C, otherwise x_u is 0) satisfying the following : for all vertices u,v * the sum of the x_w for w in the closed neighbourhood of u is at least 1 * the sum of the x_w for w in the symmetric difference of the closed neighbourhoods of u and v is at least 1. Of course, it is interesting to find an identifying code with the smallest possible cardinality. But in general this is a NP-hard problem. A way to obtain bounds on the minimal cardinality is to consider the associated linear problem where the weights x_u are fractional. In the case of vertex-transitive graphs, the minimal cardinality for the fractional case can only take two values which depend on the number of vertices, the degree of the graph and the smallest symmetric difference between any two closed neighbourhoods. We show that for an infinite family of graphs the bound is tight and for another another the bound is far too be reached. [less ▲] Detailed reference viewed: 45 (18 ULg)Some properties of abelian return words Rigo, Michel ; Salimov, Pavel ; Vandomme, Elise in Journal of Integer Sequences (2013), 16 We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in ... [more ▼] We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the 2-automatic Thue--Morse word. We also investigate the relationship existing between abelian complexity and finiteness of the set of abelian returns to all prefixes. We end this paper by considering the notion of abelian derived sequence. It turns out that, for the Thue--Morse word, the set of abelian derived sequences is infinite. [less ▲] Detailed reference viewed: 142 (40 ULg)2-abelian complexity of the Thue-Morse sequence Rigo, Michel ; Vandomme, Elise Scientific conference (2012, December 14) Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of ... [more ▼] Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. It is trivially abelian periodic and its (1)-abelian complexity takes only two values. The aim of this talk is to explain how to compute the 2-abelian complexity a(n) of the Thue-Morse word, showing in particular that it is unbounded. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a recent work of Madill and Rampersad where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will also explain why the usual logical framework introduced by Büchi and popularized by Bruyère (indeed, automatic sequences can be characterized in an extension of the Presburger arithmetic) and the recent work of Charlier et al. about "automatic theorem-proving" of properties of automatic sequences cannot be applied to these questions related to abelian complexity. [less ▲] Detailed reference viewed: 153 (40 ULg)Constant 2-labelling of weighted cycles ; Vandomme, Elise Conference (2012, November) We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2 ... [more ▼] We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2-coloring (black and white) of its vertex set which preserves the sum of the weight of black vertices under some automorphisms. In this manuscript, we study this problem on weighted complete graphs and on weighted cycles. Our results on cycles allow us to determine (r,a,b)-codes in Z^2 whenever |a-b|>4 and r>1. [less ▲] Detailed reference viewed: 26 (5 ULg)Some properties of abelian return words (long abstract) Rigo, Michel ; Salimov, Pavel ; Vandomme, Elise Conference (2012, September 11) We investigate some properties of abelian return words as recently introduced by Puzynina and Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the ... [more ▼] We investigate some properties of abelian return words as recently introduced by Puzynina and Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the ﬁniteness of the set of abelian return words to all preﬁxes. We describe this set of abelian returns for the Fibonacci word but also for the 2-automatic Thue–Morse word. We also investigate the relationship existing between abelian complexity and ﬁniteness of the set of abelian returns to all preﬁxes. We end this paper by considering the notion of abelian derived sequence. It turns out that, for the Thue–Morse word, the set of abelian derived sequences is inﬁnite. [less ▲] Detailed reference viewed: 23 (8 ULg)Constant 2-labelling of a graph ; Vandomme, Elise Conference (2012, September) We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2 ... [more ▼] We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2-coloring (black and white) of its vertex set which preserves the sum of the weight of black vertices under some automorphisms. In this manuscript, we study this problem on weighted complete graphs and on weighted cycles. Our results on cycles allow us to determine (r,a,b)-codes in Z^2 whenever |a-b|>4 and r>1. [less ▲] Detailed reference viewed: 18 (3 ULg)Syntactic complexity of ultimately periodic sets of integers Vandomme, Elise Conference (2012, July) We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼] We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic. [less ▲] Detailed reference viewed: 16 (1 ULg)Coloring of the infinite grid Vandomme, Elise ; Poster (2012, May 23) We present a method that links (r,a,b)-codes in the infinite grid and particular colorings of weighted cycles, called constant 2-labellings. Detailed reference viewed: 33 (10 ULg)Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure Lacroix, Anne ; ; Rigo, Michel et al in Fundamenta Informaticae (2012), 116 We compute the cardinality of the syntactic monoid of the language 0* rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼] We compute the cardinality of the syntactic monoid of the language 0* rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic. [less ▲] Detailed reference viewed: 88 (10 ULg)Syntactic complexity of ultimately periodic sets of integers Rigo, Michel ; Vandomme, Elise Conference (2011, June) We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼] We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic. [less ▲] Detailed reference viewed: 17 (3 ULg)Syntactic complexity of ultimately periodic sets of integers Rigo, Michel ; Vandomme, Elise in Lecture Notes in Computer Science (2011), 6638 We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼] We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic. [less ▲] Detailed reference viewed: 96 (26 ULg)Complexité syntaxique d’ensembles d’entiers ultimement périodique Vandomme, Elise Conference (2011) Detailed reference viewed: 52 (15 ULg) |
||