CanaDAM 2013
Université Memorial de Terre-Neuve, 10 - 13 juin 2013

Words and Recurrences
Président: Lowell Abrams (The George Washington University)

LOWELL ABRAMS, The George Washington University
A Family of Nim-Like Arrays: The Locator Theorem  [PDF] [SLIDES]

In the context of a certain family of Nim-like arrays which are recursively generated in a manner related to the operation of Nim-addition, we study a property we call the ``locator property" which refers to a kind of self-referential relationship between entries and their indices. We prove that the locator property holds for almost all pairs of entries in six of the arrays in the family, and give computational evidence that this is not the case for other arrays in the family.

MOUSAVI HAJI SEYYED HAMOON, University of Waterloo
Repetition Avoidance in Circular Factors  [PDF] [SLIDES]

We consider the following novel variation on a classical avoidance problem from combinatorics on words: instead of avoiding repetitions in all factors of a word, we avoid repetitions in all factors where each individual factor is considered as a ``circular word''. We determine the best possible avoidance exponent for alphabet size $2$ and $3$, and provide a lower bound for larger alphabets. This is a joint work with Jeffrey Shallit.

RUSSELL HENDEL, Towson University
Ruskey's Open Problem on Hofstadter's $Q$ Function  [PDF] [SLIDES]

Hofstadter’s Q function, $Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))$, is a nested recursion. Ruskey gives solutions to this recursion that have quasi-period 3. Hendel gives solutions that have exact period $e$ for any positive even number $e>0.$ Certain solutions have features not present in traditional recursions. This necessitates developing and standardizing notational, language and proof methods that can describe these features. The presentation will explore examples, theorems,conjectures and proof methods with the following features: i) A solution $\{s_i\}_{i>0}$ has \emph{quasi-period} $n$ meaning that the subsequences $\{s_{kn+i}\}_{k\ge0}$ with $0 \le i<n$ are constant, linear, or geometric sequences or linear homogeneous recursions with possibly bounded, (predictable) perturbations.

SAHAND SABA, University of Victoria
Non-Trivial Decidable Nested Recurrence Relations  [PDF] [SLIDES]

The question of decidability of nested recurrence relations has been studied by Celaya and Ruskey in their 2012 paper, where an example of an undecidable nested recurrence relation is given. In this talk we discuss a general result about decidable nested recurrence relations satisfying two boundedness conditions, and use it to prove the decidability of a class of non-trivial nested recurrence relations over integers of the form $G(n) = G(n-\sum_{i=1}^{K}\alpha_{i}G(n-i))$. We also discuss the decidability of certain unbounded nested recurrence relations.

(Joint research with Frank Ruskey.)


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Memorial de Terre-Neuve