Browse ORBi by ORBi project

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

A note on abelian returns in rotation words ; Rigo, Michel ; Salimov, Pavel in Theoretical Computer Science (2014), 528 Pursuing the study started by Rigo, Salimov and Vandomme, we use elementary number-theoretic techniques to characterize rotation words having a finite set of abelian returns to all prefixes. We also make ... [more ▼] Pursuing the study started by Rigo, Salimov and Vandomme, we use elementary number-theoretic techniques to characterize rotation words having a finite set of abelian returns to all prefixes. We also make the connection between the three gap theorem and the number of semi-abelian returns for Sturmian words, simplifying some arguments developed by Puzynina and Zamboni. [less ▲] Detailed reference viewed: 118 (17 ULg)Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words Rigo, Michel ; Salimov, Pavel in Lecture Notes in Computer Science (2013), 8079 The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u. Based on this classical notion, we introduce the m-binomial equivalence of two words refining the ... [more ▼] The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u. Based on this classical notion, we introduce the m-binomial equivalence of two words refining the abelian equivalence. The m-binomial complexity of an infinite word x maps an integer n to the number of m-binomial equivalence classes of factors of length n occurring in x. We study the first properties of m-binomial equivalence. We compute the m-binomial complexity of the Sturmian words and of the Thue-Morse word. We also mention the possible avoidance of 2-binomial squares. [less ▲] Detailed reference viewed: 81 (24 ULg)On the Number of Abelian Bordered Words ; Rigo, Michel ; Salimov, Pavel in Lecture Notes in Computer Science (2013), 7907 In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible ... [more ▼] In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible symmetric Motzkin paths and paths in Z not returning to the origin. This study can be extended to abelian unbordered words over an arbitrary alphabet and we derive expressions to compute the number of these words. In particular, over a 3-letter alphabet, the connection with paths in the triangular lattice is made. Finally, we study the lengths of the abelian unbordered factors occurring in the Thue--Morse word. [less ▲] Detailed reference viewed: 73 (14 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: 148 (41 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) |
||