Department of Mathematics and Statistics http://hdl.handle.net/10680/289 2019-07-16T14:06:21Z 2019-07-16T14:06:21Z Suffix conjugates for a class of morphic subshifts Currie, James D. Rampersad, Narad Saari, Kalle http://hdl.handle.net/10680/1703 2019-06-20T08:01:24Z 2015-09-01T00:00:00Z 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:00Z A Characterization of Fractionally Well-Covered Graphs Currie, James Nowakowski, Richard http://hdl.handle.net/10680/1701 2019-06-20T08:01:26Z 1991-01-01T00:00:00Z A Characterization of Fractionally Well-Covered Graphs Currie, James; Nowakowski, Richard A graph is called well-covered if every maximal independent set has the same size. One generalization of independent sets in graphs is that of a fractional cover -- attach nonnegative weights to the vertices and require that for every vertex the sum of all the weights in its closed neighbourhood be at least 1. In this paper we consider and characterize fractionally well-covered graphs. 1991-01-01T00:00:00Z Avoiding Patterns in the Abelian Sense Currie, J. Linek, V. http://hdl.handle.net/10680/1699 2019-06-20T08:01:25Z 2001-08-01T00:00:00Z Avoiding Patterns in the Abelian Sense Currie, J.; Linek, V. We classify all 3 letter patterns that are avoidable in the abelian sense. A short list of four letter patterns for which abelian avoidance is undecided is given. Using a generalization of Zimin words we deduce some properties of ω-words avoiding these patterns. 2001-08-01T00:00:00Z Words without Near-Repetitions Currie, J. Bendor-Samuel, A. http://hdl.handle.net/10680/1697 2019-06-20T08:01:22Z 1992-06-01T00:00:00Z Words without Near-Repetitions Currie, J.; Bendor-Samuel, A. We find an infinite word w on four symbols with the following property: Two occurrences of any block in w must be separated by more than the length of the block. That is, in any subword of w of the form xyx, the length of y is greater than the length of x. This answers a question of C. Edmunds connected to the Burnside problem for groups. 1992-06-01T00:00:00Z A direct proof of a result of Thue Currie, James D. http://hdl.handle.net/10680/1696 2019-06-12T08:01:22Z 1984-01-01T00:00:00Z A direct proof of a result of Thue Currie, James D. 1984-01-01T00:00:00Z The Complexity of the Simplex Algorithm Currie, James http://hdl.handle.net/10680/1695 2019-07-12T20:35:11Z 1984-08-01T00:00:00Z The Complexity of the Simplex Algorithm Currie, James The thesis begins by giving background in linear programming and Simplex methods. Topics covered include the duality theorem, Lemke's algorithm, and the pathological programs of Klee-Minty. Because of the bad behaviour of Klee-Minty programs, the behaviour of the Simplex algorithm is only good on average. To take such an average, certain assumptions on the distribution of linear programs are introduced and discussed. A geometrical meaning is given for the number of steps Lemke's algorithm takes to solve a program. This gives rise to a formula bounding the average number of steps taken. This formula is heuristically justified in an original way. The formula is combinatorially simplified, to get a bound on the complexity of Simplex. 1984-08-01T00:00:00Z Class Numbers and Biquadratic Reciprocity Williams, Kenneth S. Currie, James D. http://hdl.handle.net/10680/1694 2019-06-06T08:00:12Z 1982-01-01T00:00:00Z Class Numbers and Biquadratic Reciprocity Williams, Kenneth S.; Currie, James D. The research of the first author was supported by Natural Sciences and Engineering Research Council Canada Grant No. A-7233, while that of the second was supported by a Natural Sciences and Engineering Research Council Canada Undergraduate Summer Research Award. 1982-01-01T00:00:00Z Non repetitive walks in graphs and digraphs Currie, James Daniel http://hdl.handle.net/10680/1654 2019-04-11T21:33:04Z 1987-06-01T00:00:00Z 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:00Z Skeleton Cave, Leigh Woods, Bristol Mullan, G. J. Meiklejohn, C. Babb, J. http://hdl.handle.net/10680/1578 2019-06-24T16:06:51Z 2017-01-01T00:00:00Z 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:00Z Introduction: Special volume in honor of Jeffrey Shallit on the occasion of his 60th birthday Rampersad, Narad http://hdl.handle.net/10680/1419 2019-06-24T21:29:19Z 2018-03-01T00:00:00Z Introduction: Special volume in honor of Jeffrey Shallit on the occasion of his 60th birthday Rampersad, Narad 2018-03-01T00:00:00Z