Browse ORBi by ORBi project

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

On the number of abelian bordered words (with an example of automatic theorem-proving) ; ; Rigo, Michel et al in International Journal of Foundations of Computer Science (2014), 8 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 $\mathbb{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 characterize the lengths of the abelian unbordered factors occurring in the Thue--Morse word using some kind of automatic theorem-proving provided by a logical characterization of the $k$-automatic sequences. [less ▲] Detailed reference viewed: 15 (3 ULg)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: 116 (17 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: 72 (14 ULg)Enumeration and decidable properties of automatic sequences Charlier, Emilie ; ; in International Journal of Foundations of Computer Science (2012), 23(5), 1035-1066 We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼] We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲] Detailed reference viewed: 20 (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)Enumeration and decidable properties of automatic sequences Charlier, Emilie ; ; in Actes de Numération 2011 (2011, June) We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences ... [more ▼] We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences de ned in terms of Pisot numeration systems. [less ▲] Detailed reference viewed: 22 (3 ULg)The growth function of S-recognizable sets Charlier, Emilie ; in Theoretical Computer Science (2011), 412(39), 5400-5408 A set X ⊆ N is S-recognizable for an abstract numeration system S, if the set rep_S (X) of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set ... [more ▼] A set X ⊆ N is S-recognizable for an abstract numeration system S, if the set rep_S (X) of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set is always either Θ((log(n))^(c−df) n^f ) where c, d ∈ N and f ≥ 1, or Θ(n^r θ^(Θ(n^q))), where r, q ∈ Q with q ≤ 1. If the number of words of length n in the numeration language is bounded by a polynomial, then the growth function of an S-recognizable set is Θ(nr ), where r ∈ Q with r ≥ 1. Furthermore, for every r ∈ Q with r ≥ 1, we can provide an abstract numeration system S built on a polynomial language and an S-recognizable set such that the growth function of X is Θ(n^r ). For all positive integers k and ℓ, we can also provide an abstract numeration system S built on an exponential language and an S-recognizable set such that the growth function of X is Θ((log(n))^k n^ℓ). [less ▲] Detailed reference viewed: 21 (7 ULg)Enumeration and decidable properties of automatic sequences Charlier, Emilie ; ; in Lecture Notes in Computer Science (2011), 6795 We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼] We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲] Detailed reference viewed: 21 (4 ULg) |
||