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.

NARAD RAMPERSAD, University of Winnipeg
Extremal words in the shift orbit closure of a morphic sequence  [PDF]

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.

LUKE SCHAEFFER, University of Waterloo
Abelian powers in automatic sequences are not always automatic  [PDF]

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$.

JEFFREY SHALLIT, University of Waterloo
Decidability in Automatic Sequences  [PDF] [SLIDES]

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.