 CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013 français conference home canadam home

Decidability in Automatic and Related Sequences
Organizer and Chair: Jeffrey Shallit (University of Waterloo)
[PDF]

JAMES CURRIE, University of Winnipeg
Abelian powers and patterns in words: problems and perspectives  [PDF] [SLIDES]

Two words are abelian equivalent if one is a permutation of the other. Thus "red" and "der" are abelian equivalent, and "redder" is then an abelian square. In other words, "redder" is an abelian instance of the pattern $xx$, with $x=red\sim der$. Erd\"os asked if there exists an infinite word over a finite alphabet avoiding abelian squares. Since then, many more general questions have arisen, including the study of abelian $k$-powers, where $k$ may be fractional, and decision problems related to abelian instances of more general patterns. I will present an overview of the results in this area.

DANIEL GOC, University of Waterloo
Automatic Theorem-Proving in Automatic Sequences  [PDF] [SLIDES]

We describe the implementation of a a decision procedure for certain properties of automatic sequences, using finite automata and a package for manipulating them. We highlight a range of successful applications of the technique, including the determination of the optimal repetition avoidance exponent for Leech's sequence.

Let $x$ be an infinite word over an alphabet $A$; let $\sigma$ be a total order on $A$; and let $b$ be a letter of $A$. A word $y$ in the shift orbit closure of $x$ is "extremal" if it is the lexicographically least word (with respect to $\sigma$) starting with $b$ in the shift orbit closure of $x$. We show that if $x$ is morphic (i.e., $x=g(f^\omega(a))$ for some morphisms $f,g$) and $f$ and $g$ satisfy certain conditions, then every extremal word of $x$ is morphic. In particular, the extremal words of pure morphic binary words are morphic.
An abelian square is a word of the form $x x'$, where $x'$ is a permutation of $x$, such as the English word "reappear". This is generalized to abelian $m$'th powers. In this talk I prove that, for all integers $m \geq 2$, the occurrences of abelian $m$th powers in a particular automatic sequence (the regular paperfolding word) is not automatic. It follows that abelian repetitions cannot be expressed in the logical theory $(\mathbb{N}, +, <, V_k)$, where $V_k(n)$ is the highest power of $k$ dividing $n$.
A sequence $(a(n))$ over a finite alphabet is said to be $k$-automatic if there is a deterministic finite automaton that takes as input an integer $n$ expressed in base $k$, and reaches a state with output $a(n)$. In this talk I will sketch a decision procedure for answering questions about such sequences, such as periodicity, repetition avoidance, recurrence, and so forth, and discuss some of its ramifications.