Publications

A list of errata is available.

Book chapters

  1. J. Shallit, N. Rampersad, "Repetitions in words". In Combinatorics, Words and Symbolic Dynamics, Cambridge, 2016.

Preprints

  1. J.-P. Allouche, N. Rampersad, J. Shallit, "Repetition threshold for binary automatic sequences".
  2. J. Currie, N. Rampersad, "The analogue of overlap-freeness for the Fibonacci morphism".
  3. J. Currie, N. Rampersad, "The lexicographically least binary rich word achieving the repetition threshold".
  4. N. Rampersad, J. Shallit, "Rudin-Shapiro sums via automata theory and logic".
  5. J. Currie, L. Dvorakova, P. Ochem, D. Opocenska, N. Rampersad, J. Shallit, "Complement avoidance in binary words".
  6. N. Rampersad, M. Wiebe, "Correlations of minimal forbidden factors of the Fibonacci word".
  7. P. Gawrychowski, M. Lange, N. Rampersad, J. Shallit, M. Szykula, "Existential length universality".

Journal publications

  1. J. Currie, L. Mol, N. Rampersad, J. Shallit, "Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers". To appear in SIAM J. Discrete Math.
  2. N. Rampersad, J. Shallit, X. Xu, "Repetition factorization of automatic sequences". To appear in Internat. J. Found. Comp. Sci.
  3. N. Rampersad, M. Wiebe, "Sums of products of binomial coefficients mod 2 and 2-regular sequences", INTEGERS 24 (2024), A24.
  4. L. Mol, N. Rampersad, J. Shallit, "Dyck words, pattern avoidance, and automatic sequences", Commun. Math. 33 (2025).
  5. J. Currie, N. Rampersad, "A small morphism giving Abelian repetition threshold less than 2", Theor. Inform. Appl. 58 (2024).
  6. A. Baranwal, J. Currie, L. Mol, P. Ochem, N. Rampersad, J. Shallit, "Antisquares and critical exponents", Discrete Math. Theoret. Comput. Sci. 25:2 (2023).
  7. J. Currie, P. Ochem, N. Rampersad, J. Shallit, "Properties of a ternary infinite word", Theor. Inform. Appl. 57 (2023).
  8. N. Rampersad, "The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word", Australas. J. Combin. 85 (2023), 150-158.
  9. N. Rampersad "Prefixes of the Fibonacci word that end with a cube", C. R. Math. Acad. Sci. Paris 361 (2023), 323-330.
  10. N. Rampersad, J. Shallit, "Congruence properties of combinatorial sequences via Walnut and the Rowland-Yassawi-Zeilberger automaton", Electron. J. Combin., 29 (2022), Article P3.36. Here are the automata in Walnut format used in this paper.
  11. M. Jahannia, M. Mohammad-noori, N. Rampersad, M. Stipulanti, "Closed Ziv-Lempel factorization of the m-bonacci words", Theoret. Comput. Sci., 918 (2022), 32-47.
  12. I. Kaye, N. Rampersad, "The abelian complexity of infinite words and the Frobenius problem", INTEGERS 21 (2021), Article A46.
  13. M. Milosevic, N. Rampersad, "Squarefree words with interior disposable factors", Theoret. Comput. Sci. 863 (2021), 120-126.
  14. D. Gabric, N. Rampersad, J. Shallit, "An inequality for the number of periods in a word", Internat. J. Found. Comp. Sci. 32 (2021), 597--614. Erratum.
  15. L. Mol, N. Rampersad, "Lengths of extremal square-free ternary words", Contrib. Discrete Math. 16 (2021), 8--19.
  16. L. Mol, N. Rampersad, J. Shallit, "Extremal overlap-free and extremal beta-free binary words", Electron. J. Combinatorics 27 (2020), Article P4.42.
  17. L. Mol, N. Rampersad, "The weak circular repetition threshold over large alphabets", Theor. Inform. Appl. 54 (2020), Article 6.
  18. J. Currie, L. Mol, N. Rampersad, "The number of threshold words on n letters grows exponentially for every n ≥ 27", J. Integer Sequences 23 (2020), Article 20.3.1
  19. J. Currie, L. Mol, N. Rampersad, "The repetition threshold for binary rich words", Discrete Math. Theoret. Comput. Sci. 22 (no. 1) (2020), Article 6.
  20. L. Mol, N. Rampersad, J. Shallit, M. Stipulanti, "Cobham's theorem and automaticity", Internat. J. Found. Comp. Sci. 30 (2019), 1363-1379.
  21. J. Currie, T. Harju, P. Ochem, N. Rampersad, "Some further results on squarefree arithmetic progressions in infinite words", Theoret. Comput. Sci. 799 (2019), 140-148.
  22. M. Jahannia, M. Mohammad-noori, N. Rampersad, M. Stipulanti, "Palindromic Ziv-Lempel and Crochemore factorizations of m-bonacci infinite words", Theoret. Comput. Sci. 790 (2019), 16-40.
  23. J. Currie, L. Mol, N. Rampersad, "Circular repetition thresholds on some small alphabets: Last cases of Gorbunova's conjecture", Electron. J. Combinatorics 26 (2019), Article P2.31.
  24. N. Rampersad, J. Shallit, E. Vandomme, "Critical exponents of infinite balanced words", Theoret. Comput. Sci. 777 (2019), 454-463.
  25. N. Rampersad, M. Stipulanti, "The formal inverse of the period-doubling sequence", J. Integer Sequences 21 (2018), Article 18.9.1.
  26. J. Currie, L. Mol, N. Rampersad, "Avoidance bases for formulas with reversal", Theoret. Comput. Sci. 738 (2018), 25-41.
  27. A. Borchert, N. Rampersad, "Permutation complexity of images of Sturmian words by marked morphisms", Discrete Math. Theoret. Comput. Sci 20 (2018), Article 20-1-20.
  28. J. Nicholson, N. Rampersad, "Improved estimates for the number of privileged words", J. Integer Sequences 21 (2018), Article 18.3.8.
  29. C. Krawchuk, N. Rampersad, "Cyclic complexity of some infinite words and generalizations", INTEGERS 18a (2018), Article A12.
  30. J. Currie, L. Mol, N. Rampersad, "On avoidability of formulas with reversal", Theor. Inform. Appl. 51 (2018), 181-189.
  31. J. Nicholson, N. Rampersad, "The Frobenius problem for the shuffle operation", Semigroup Forum 96 (2018), 160-177.
  32. J. Currie, L. Mol, N. Rampersad, "A family of formulas with reversal of high avoidability index", Internat. J. Algebra and Computation 27 (2017), 477-494.
  33. J. Nicholson, N. Rampersad, "Non-repetitive complexity of infinite words", Discrete Appl. Math. 208 (2016), 114-122.
  34. S. Camungol, N. Rampersad, "Avoiding approximate repetitions with respect to the longest common subsequence distance", Involve 9 (2016), 657-666.
  35. J. Currie, N. Rampersad, "Growth rate of binary words avoiding xxx^R", Theoret. Comput. Sci. 609 (2016), 456-468. Errata.
  36. A. Borchert, N. Rampersad, "Words with many palindrome pair factors", Electron. J. Combinatorics 22 (2015), Paper \#P4.23.
  37. J. Currie, N. Rampersad, "Binary words avoiding xx^Rx and strongly unimodal sequences", J. Integer Sequences 15 (2015), Article 15.10.3.
  38. J. Currie, N. Rampersad, K. Saari, "Suffix conjugates for a class of morphic subshifts", Ergodic Theory Dynam. Systems 35 (2015), 1767-1782.
  39. P. Lafrance, N. Rampersad, R. Yee, "Some properties of a Rudin--Shapiro-like sequence", Adv. Appl. Math. 63 (2015), 19-40.
  40. D. Goc, N. Rampersad, M. Rigo, P. Salimov, "On the number of abelian bordered words (with an example of automatic theorem proving)", Internat. J. Found. Comp. Sci. 25 (2014), 1097-1110.
  41. F. Blanchet-Sadri, N. Fox, N. Rampersad, "On the asymptotic abelian complexity of morphic words", Adv. Appl. Math. 61 (2014), 46-84.
  42. N. Rampersad, M. Rigo, P. Salimov, "A note on abelian returns in rotation words", Theoret. Comput. Sci. 528 (2014), 101-107.
  43. F. Blanchet-Sadri, J. Currie, N. Fox, N. Rampersad, "Abelian complexity of fixed point of morphism 0→012, 1→02, 2→1", INTEGERS 14 (2014), A11.
  44. J. Currie, N. Rampersad, K. Saari, L. Zamboni, "Extremal words in morphic subshifts", Discrete Math. 322 (2014), 53-60.
  45. S. Camungol, N. Rampersad, "Concerning Kurosaki's squarefree word", J. Integer Seq. 16 (2013), Article 13.9.4, 6 pages.
  46. N. Rampersad, E. Vaslet, "On highly repetitive and power free words", J. Integer Seq. 16 (2013), Article 13.2.7, 17 pages.
  47. B. Madill, N. Rampersad, "The abelian complexity of the paperfolding word", Discrete Math. 313 (2013), 831-838.
  48. A. Lacroix, N. Rampersad, "Automaticity of primitive words and irreducible polynomials", Discrete Math. Theoret. Comput. Sci., 15 (2013), 29-36.
  49. D. Henshall, N. Rampersad, J. Shallit, "Shuffling and unshuffling", Bull. Europ. Assoc. Theoret. Comput. Sci. 107 (2012), 131-142.
  50. E. Charlier, N. Rampersad, J. Shallit, "Enumeration and decidable properties of automatic sequences", Internat. J. Found. Comp. Sci. 23 (2012), 1035-1066.
  51. M. Domaratzki, N. Rampersad, "Abelian primitive words", Internat. J. Found. Comp. Sci. 23 (2012), 1021-1033.
  52. N. Rampersad, J. Shallit, Z. Xu, "The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages", Fundamenta Informaticae 116 (2012), 223-236.
  53. A. Lacroix, N. Rampersad, M. Rigo, E. Vandomme, "Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure", Fundamenta Informaticae 116 (2012), 175-187.
  54. E. Charlier, A. Lacroix, N. Rampersad, "Multi-dimensional sets recognizable in all abstract numeration systems", Theor. Inform. Appl. 46 (2012), 51-65.
  55. J. Currie, N. Rampersad, "Fixed points avoiding Abelian k-powers", J. Combin. Theory Ser. A 119 (2012), 942-948. Errata.
  56. E. Charlier, N. Rampersad, "The growth function of S-recognizable sets", Theoret. Comput. Sci. 412 (2011), 5400-5408.
  57. E. Charlier, N. Rampersad, M. Rigo, L. Waxweiler, "The minimal automaton recognizing mN in a linear numeration system", Integers 11B (2011), A4.
  58. N. Rampersad, "Further applications of a power series method for pattern avoidance", Electron. J. Combinatorics. 18(1) (2011), #P134.
  59. J. Currie, N. Rampersad, "Recurrent words with constant Abelian complexity", Adv. Appl. Math. 47 (2011), 116-124.
  60. J. Currie, N. Rampersad, "A proof of Dejean's conjecture", Math. Comp. 80 (2011), 1063-1070. Erratum.
  61. N. Rampersad, J. Shallit, M.-w. Wang, "Inverse star, borders, and palstars", Inform. Process. Lett. 111 (2011), 420-422.
  62. B. Blakeley, F. Blanchet-Sadri, J. Gunter, N. Rampersad, "On the complexity of deciding avoidability of sets of partial words", Theoret. Comput. Sci. 411 (2010), 4263-4271.
  63. P. Gawrychowski, D. Krieger, N. Rampersad, J. Shallit, "Finding the growth rate of a regular or context-free language in polynomial time", Internat. J. Found. Comp. Sci. 21 (2010), 597-618.
  64. J. Currie, N. Rampersad, "Cubefree words with many squares", Discrete Math. Theoret. Comput. Sci. 12 (2010), 29-34.
  65. J. Currie, N. Rampersad, "Infinite words containing squares at every position", Theor. Inform. Appl. 44 (2010), 113-124.
  66. N. Rampersad, J. Shallit, "Detecting patterns in finite regular and context-free languages", Inform. Process. Lett. 110 (2010), 108-112.
  67. J. Currie, N. Rampersad, "Dejean's conjecture holds for n ≥ 27", Theor. Inform. Appl. 43 (2009), 775-778.
  68. T. Anderson, J. Loftus, N. Rampersad, N. Santean, J. Shallit, "Detecting palindromes, patterns, and borders in regular languages", Inform. and Comput. 207 (2009), 1096-1118.
  69. J.-Y. Kao, N. Rampersad, J. Shallit, "On NFA's where all states are final, initial, or both", Theoret. Comput. Sci. 410 (2009), 5010-5021.
  70. J. Currie, N. Rampersad, "Dejean's conjecture holds for n ≥ 30", Theoret. Comput. Sci. 410 (2009), 2885-2888.
  71. J.-P. Allouche, N. Rampersad, J. Shallit, "Periodicity, repetitions, and orbits of an automatic sequence", Theoret. Comput. Sci. 410 (2009), 2795-2803.
  72. J. Currie, N. Rampersad, "There are k-uniform cubefree binary morphisms for all k ≥ 0", Discrete Appl. Math. 157 (2009), 2548-2551.
  73. N. Rampersad, B. Ravikumar, N. Santean, J. Shallit, "State complexity of unique rational operations", Theoret. Comput. Sci. 410 (2009), 2431-2441.
  74. D. Krieger, A. Miller, N. Rampersad, B. Ravikumar, J. Shallit, "Decimations of languages and state complexity", Theoret. Comput. Sci. 410 (2009), 2401-2409.
  75. N. Rampersad, "Avoiding sufficiently large binary patterns", Bull. Europ. Assoc. Theoret. Comput. Sci. 95 (2008), 241-245.
  76. J. Currie, N. Rampersad, "For each α > 2 there is an infinite binary word with critical exponent α", Electron. J. Combinatorics 15 (2008), #N34.
  77. P. Ochem, N. Rampersad, J. Shallit, "Avoiding approximate squares", Internat. J. Found. Comp. Sci. 19 (2008), 633-648.
  78. B. Adamczewski, N. Rampersad, "On patterns occurring in binary algebraic numbers", Proc. Amer. Math. Soc. 136 (2008), 3105-3109.
  79. J.-Y. Kao, N. Rampersad, J. Shallit, M. Silva, "Words avoiding repetitions in arithmetic progressions", Theoret. Comput. Sci. 391 (2008), 126-137.
  80. N. Rampersad, "On the context-freeness of the set of words containing overlaps", Inform. Process. Lett. 102 (2007), 74-78.
  81. J. Currie, N. Rampersad, J. Shallit, "Binary words containing infinitely many overlaps", Electron. J. Combinatorics 13 (2006), #R82.
  82. N. Rampersad, "The state complexity of L2 and Lk", Inform. Process. Lett. 98 (2006), 231-234.
  83. S. Brown, N. Rampersad, J. Shallit, T. Vasiga, "Squares and overlaps in the Thue-Morse sequence and some variants", Theor. Inform. Appl. 40 (2006), 473-484.
  84. N. Rampersad, "Words avoiding 7/3-powers and the Thue-Morse morphism", Internat. J. Found. Comp. Sci. 16 (2005), 755-766.
  85. N. Rampersad, J. Shallit, M.-w. Wang, "Avoiding large squares in infinite binary words", Theoret. Comput. Sci. 339 (2005), 19-34.
  86. J.-P. Allouche, N. Rampersad, J. Shallit, "On integer sequences whose first iterates are linear", Aequationes Math. 69 (2005), 114-127.
  87. N. Rampersad, J. Shallit, "Words avoiding reversed subwords", J. Combin. Math. Combin. Comput. 54 (2005), 157-164.
  88. A. Aberkane, J. Currie, N. Rampersad, "The number of ternary words avoiding abelian cubes grows exponentially", J. Integer Seq. 7 (2004), Article 04.2.7, 13 pages.

Conference publications

  1. N. Rampersad, J. Shallit, "Rudin-Shapiro sums via automata theory and logic". In Proceedings of WORDS'23, Vol. 13899 of Lecture Notes in Computer Science, pp. 233--246, Springer, 2023.
  2. L. Mol, N. Rampersad, J. Shallit, "Dyck words, pattern avoidance, and automatic sequences". In Proceedings of WORDS'23, Vol. 13899 of Lecture Notes in Computer Science, pp. 220--232, Springer, 2023.
  3. P. Gawrychowski, M. Lange, N. Rampersad, J. Shallit, M. Szykula, "Existential length universality". In Proceedings of STACS'20, Vol. 154 of LIPIcs, Dagstuhl, 2020.
  4. T. Ng, P. Ochem, N. Rampersad, J. Shallit, "New results on pseudosquare avoidance". In Proceedings of WORDS'19, Vol. 11682 of Lecture Notes in Computer Science, pp. 264-274, Springer-Verlag, 2019.
  5. A. Rajasekaran, N. Rampersad, J. Shallit, "Overpals, underlaps, and underpals". In Proceedings of WORDS'17, Vol. 10434 of Lecture Notes in Computer Science, pp. 17-29, Springer-Verlag, 2017.
  6. J. Currie, N. Rampersad, K. Saari, "Extremal words in the shift orbit closure of a morphic sequence". In Proceedings of DLT'13, Vol. 7907 of Lecture Notes in Computer Science, pp. 143-154, Springer-Verlag, 2013.
  7. N. Rampersad, M. Rigo, P. Salimov, "On the number of abelian bordered words". In Proceedings of DLT'13, Vol. 7907 of Lecture Notes in Computer Science, pp. 420-432, Springer-Verlag, 2013.
  8. N. Rampersad, J. Shallit, A. Shur, "Fife's Theorem for 7/3-powers". In Proceedings of WORDS'11.
  9. N. Rampersad, E. Vaslet, "On highly repetitive and power free words". In Proceedings of DLT'11, Vol. 6795 of Lecture Notes in Computer Science, pp. 441-451, Springer-Verlag, 2011.
  10. E. Charlier, N. Rampersad, J. Shallit, "Enumeration and decidable properties of automatic sequences". In Proceedings of DLT'11, Vol. 6795 of Lecture Notes in Computer Science, pp. 165-179, Springer-Verlag, 2011.
  11. M. Domaratzki, N. Rampersad, "Abelian primitive words". In Proceedings of DLT'11, Vol. 6795 of Lecture Notes in Computer Science, pp. 204-215, Springer-Verlag, 2011.
  12. E. Charlier, N. Rampersad, M. Rigo, L. Waxweiler, "Structure of the minimal automaton of a numeration language and applications to state complexity". In Proceedings of Journees Montoises D'Informatique Theorique 2010.
  13. E. Charlier, N. Rampersad, M. Rigo, L. Waxweiler, "State complexity of testing divisibility". In Proceedings of DCFS'10.
  14. F. Blanchet-Sadri, B. Blakeley, J. Gunter, N. Rampersad, "On the complexity of deciding avoidability of sets of partial words". In Proceedings of DLT'09 , Vol. 5583 of Lecture Notes in Computer Science, pp. 113-124, Springer-Verlag, 2009.
  15. J. Currie, N. Rampersad, "Infinite words containing squares at every position". In Proceedings of Journees Montoises D'Informatique Theorique 2008.
  16. P. Gawrychowski, D. Krieger, N. Rampersad, J. Shallit, "Finding the growth rate of a regular or context-free language in polynomial time". In Proceedings of DLT'08, Vol. 5257 of Lecture Notes in Computer Science, pp. 339-358, Springer-Verlag, 2008.
  17. T. Anderson, N. Rampersad, N. Santean, J. Shallit, "Finite automata, palindromes, powers, and patterns". In Proceedings of LATA'08 , Vol. 5196 of Lecture Notes in Computer Science, pp. 52-63, Springer-Verlag, 2008.
  18. D. Krieger, P. Ochem, N. Rampersad, J. Shallit, "Avoiding approximate squares". In Proceedings of DLT'07 , Vol. 4588 of Lecture Notes in Computer Science, pp. 278-289, Springer-Verlag, 2007.
  19. S. Brown, N. Rampersad, J. Shallit, T. Vasiga, "Squares and overlaps in the Thue-Morse sequence and some variants", In Proceedings of WACAM'04, LaRIA Technical Report 2004-07, pp. 15-20, 2004.
  20. N. Rampersad, "Words avoiding 7/3-powers and the Thue-Morse morphism", In Proceedings of DLT'04 , Vol. 3340 of Lecture Notes in Computer Science, pp. 357-367, Springer-Verlag, 2004.
  21. N. Rampersad, J. Shallit, M.-w. Wang, "Avoiding large squares in infinite binary words". In Proceedings of WORDS'03, TUCS General Publication No. 27, pp. 185-197, 2003.

Thesis

  1. N. Rampersad, Overlap-Free Words and Generalizations. Ph.D. thesis, University of Waterloo, 2007.