Department of Mathematics and Statistics
http://hdl.handle.net/10680/289
2019-04-25T15:48:44ZNon repetitive walks in graphs and digraphs
http://hdl.handle.net/10680/1654
Non repetitive walks in graphs and digraphs
Currie, James Daniel
A word $w$ over alphabet $\Sigma$ is {\em non-repetitive} if we cannot write $w=abbc$, $a,b,c\in\Sigma^*$, $b\ne\epsilon$. That is, no subword of $w$ appears twice in a row in $w$. In 1906, Axel Thue, the Norwegian number theorist, showed that arbitrarily long non-repetitive words exist on a three letter alphabet.
Call a graph or digraph $G$ {\em versatile} if arbitrarily long non-repetitive words can be walked on $G$. This work deals with two questions:
\begin{enumerate}
\item Which graphs are versatile?
\item Which digraphs are versatile?
\end{enumerate}
Our results concerning versatility of digraphs may be considered to give information about the structure of non-repetitive words on finite alphabets.
We attack these questions as follows:
\begin{enumerate}
\item We introduce a partial order on digraphs called {\em mimicking}. We show that if digraph $G$ mimics digraph $H$, then if $H$ is versatile, so is $G$.
\item We then produce two sets of digraphs MIN and MAX, and show that every digraph of MIN is versatile. (These digraphs are intended to be minimal in the mimicking partial order with respect to being versatile.) and no digraph of MAX is versatile. (The digraphs of MAX are intended to be maximal with respect to not being versatile.)
\item In a lengthy classification, we show that every digraph either mimics a digraph of MIN, and hence is versatile, or "reduces" to some digraph mimicked by a digraph of MAX, and hence is not versatile.
We conclude that a digraph is versatile exactly when it mimics one of the digraphs in the finite set MIN. The set MIN contains eighty-nine (89) digraphs, and the set MAX contains twenty-five (25) individual digraphs, and one infinite family of digraphs.
\end{enumerate}
PhD thesis of James Daniel Currie (University of Calgary, 1987)
1987-06-01T00:00:00ZSkeleton Cave, Leigh Woods, Bristol
http://hdl.handle.net/10680/1578
Skeleton Cave, Leigh Woods, Bristol
Mullan, G. J.; Meiklejohn, C.; Babb, J.
An account is given of the discovery and excavation of this small cave in the 1960s. It is recorded that archaeological finds were made, but of these, only a single human mandible can now be traced. Radiocarbon dating shows the specimen to be early Neolithic in age; a metrical analysis was less conclusive.
2017-01-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