Narad Rampersad
http://hdl.handle.net/10680/1355
2020-08-09T09:23:56ZA family of formulas with reversal of high avoidability index
http://hdl.handle.net/10680/1755
A family of formulas with reversal of high avoidability index
Currie, James; Mol, Lucas; Rampersad, Narad
We present an infinite family of formulas with reversal whose avoidability index is bounded between 4 and 5, and we show that several members of the family have avoidability index 5. This family is particularly interesting due to its size and the simple structure of its members. For each k ∈ {4,5}, there are several previously known avoidable formulas (without reversal) of avoidability index k, but they are small in number and they all have rather complex structure.
2017-01-01T00:00:00ZSuffix conjugates for a class of morphic subshifts
http://hdl.handle.net/10680/1703
Suffix conjugates for a class of morphic subshifts
Currie, James D.; Rampersad, Narad; Saari, Kalle
Let A be a finite alphabet and f: A^* --> A^* be a morphism with an iterative fixed point f^\omega(\alpha), where \alpha{} is in A. Consider the subshift (X, T), where X is the shift orbit closure of f^\omega(\alpha) and T: X --> X is the shift map. Let S be a finite alphabet that is in bijective correspondence via a mapping c with the set of nonempty suffixes of the images f(a) for a in A. Let calS be a subset S^N be the set of infinite words s = (s_n)_{n\geq 0} such that \pi(s):= c(s_0)f(c(s_1)) f^2(c(s_2))... is in X. We show that if f is primitive and f(A) is a suffix code, then there exists a mapping H: calS --> calS such that (calS, H) is a topological dynamical system and \pi: (calS, H) --> (X, T) is a conjugacy; we call (calS, H) the suffix conjugate of (X, T). In the special case when f is the Fibonacci or the Thue-Morse morphism, we show that the subshift (calS, T) is sofic, that is, the language of calS is regular.
2015-09-01T00:00:00ZIntroduction: Special volume in honor of Jeffrey Shallit on the occasion of his 60th birthday
http://hdl.handle.net/10680/1419
Introduction: Special volume in honor of Jeffrey Shallit on the occasion of his 60th birthday
Rampersad, Narad
2018-03-01T00:00:00ZCyclic Complexity of Some Infinite Words and Generalizations
http://hdl.handle.net/10680/1417
Cyclic Complexity of Some Infinite Words and Generalizations
Krawchuk, Colin; Rampersad, Narad
Cassaigne et al. introduced the cyclic complexity function c_x(n), which gives the number of cyclic conjugacy classes of length-n factors of a word x. We study the behavior of this function for the Fibonacci word f and the Thue–Morse word t. If φ = (1 + √5)/2, we show that lim sup_{n → 1} c_f(n)/n ≥ 2/φ² and conjecture that equality holds. Similarly, we show that lim sup_{n → 1} c_t(n)/n ≥ 2 and conjecture that
equality holds. We also propose a generalization of the cyclic complexity function and suggest some directions for further investigation. Most results are obtained by computer proofs using Mousavi’s Walnut software.
2018-03-01T00:00:00ZOverlap-Free Words and Generalizations
http://hdl.handle.net/10680/1414
Overlap-Free Words and Generalizations
Rampersad, Narad
The study of combinatorics on words dates back at least to the beginning of the
20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains no squares (identical ad-
jacent blocks) xx. This result was eventually used to solve some longstanding open problems in algebra and has remarkable connections to other areas of mathematics and computer science as well.
This thesis will consider several different generalizations of Thue’s work. In particular
we shall study the properties of infinite words avoiding various types of repetitions.
In Chapter 1 we introduce the theory of combinatorics on words. We present the basic definitions and give an historical survey of the area.
In Chapter 2 we consider the work of Thue in more detail. We present various well-known properties of the Thue–Morse word and give some generalizations. We examine Fife’s characterization of the infinite overlap-free words and give a simpler proof of this result. We also present some applications to transcendental number theory, generalizing a classical result of Mahler.
In Chapter 3 we generalize a result of Séébold by showing that the only infinite 7/3-power-free binary words that can be obtained by iterating a morphism are the
Thue–Morse word and its complement.
In Chapter 4 we continue our study of overlap-free and 7/3-power-free words. We discuss the squares that can appear as subwords of these words. We also show that it is possible to construct infinite 7/3-power-free binary words containing infinitely many overlaps.
In Chapter 5 we consider certain questions of language theory. In particular, we examine the context-freeness of the set of words containing overlaps. We show that over a three-letter alphabet, this set is not context-free, and over a two-letter alphabet, we show that this set cannot be unambiguously context-free.
In Chapter 6 we construct infinite words over a four-letter alphabet that avoid squares in any arithmetic progression of odd difference. Our constructions are based on properties of the paperfolding words. We use these infinite words to construct non-repetitive tilings of the integer lattice.
In Chapter 7 we consider approximate squares rather than squares. We give constructions of infinite words that avoid such approximate squares.
In Chapter 8 we conclude the work and present some open problems.
2007-01-01T00:00:00ZFurther applications of a power series method for pattern avoidance
http://hdl.handle.net/10680/1413
Further applications of a power series method for pattern avoidance
Rampersad, Narad
In combinatorics on words, a word w over an alphabet ∑ is said to avoid a pattern
p over an alphabet ∆ if there is no factor x of w and no non-erasing morphism h
from ∆* to ∑* such that h(p) = x. Bell and Goh have recently applied an algebraic
technique due to Golod to show that for a certain wide class of patterns p there
are exponentially many words of length n over a 4-letter alphabet that avoid p. We
consider some further consequences of their work. In particular, we show that any
pattern with k variables of length at least 4k is avoidable on the binary alphabet.
This improves an earlier bound due to Cassaigne and Roth.
2011-06-21T00:00:00ZThe minimal automaton recognizing mN in a linear numeration system
http://hdl.handle.net/10680/1412
The minimal automaton recognizing mN in a linear numeration system
Charlier, Émilie; Rampersad, Narad; Rigo, Michel; Waxweiler, Laurent
We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root β > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number β. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m ≥ 2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m2.
2011-12-02T00:00:00ZMulti-dimensional sets recognizable in all abstract numeration systems
http://hdl.handle.net/10680/1411
Multi-dimensional sets recognizable in all abstract numeration systems
Charlier, Émilie; Lacroix, Anne; Rampersad, Narad
We prove that the subsets of Nd that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
2011-01-01T00:00:00ZShuffling and unshuffling
http://hdl.handle.net/10680/1410
Shuffling and unshuffling
Henshall, Dane; Rampersad, Narad; Shallit, Jeffrey
We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal language theory classes, we also provide some new results and mention some open problems.
2012-01-01T00:00:00ZAutomaticity of Primitive Words and Irreducible Polynomials
http://hdl.handle.net/10680/1409
Automaticity of Primitive Words and Irreducible Polynomials
Lacroix, Anne; Rampersad, Narad
If L is a language, the automaticity function AL(n) (resp. NL(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all inputs of length at most n. We provide bounds for the automaticity of the language of primitive words and the language of unbordered words over a k-letter alphabet. We also give a bound for the automaticity of the language of base-b representations of the irreducible polynomials over a finite field. This latter result is analogous to a result of Shallit concerning the base-k representations of the set of prime numbers.
2013-01-01T00:00:00Z