References of "Rampersad, Narad"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailA note on abelian returns in rotation words
Rampersad, Narad; Rigo, Michel ULg; Salimov, Pavel ULg

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: 68 (9 ULg)
Full Text
Peer Reviewed
See detailA note on abelian returns in rotation words
Rampersad, Narad; Rigo, Michel ULg; Salimov, Pavel ULg

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: 68 (9 ULg)
Full Text
Peer Reviewed
See detailOn the Number of Abelian Bordered Words
Rampersad, Narad; Rigo, Michel ULg; Salimov, Pavel ULg

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: 57 (13 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

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: 13 (7 ULg)
Full Text
Peer Reviewed
See detailSyntactic complexity of ultimately periodic sets of integers and application to a decision procedure
Lacroix, Anne ULg; Rampersad, Narad; Rigo, Michel ULg 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: 47 (3 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

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: 20 (3 ULg)
Full Text
Peer Reviewed
See detailThe growth function of S-recognizable sets
Charlier, Emilie ULg; Rampersad, Narad

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: 14 (5 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

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: 14 (4 ULg)