Description:

We call mappings from an alphabet $\cA=\{a_1,a_2,...,a_d\}$ to the set $\cA^*=\{W=w_1w_2...w_rr\in\nats,w_i\in\cA\}$ of all finite ordered sequences comprised of letters in $\cA$, \emph{substitutions} over $\cA$. By definition, a substitution $\varphi$ maps $\cA\to\cA^*$, but it can be extended to map $\cA^*\to\cA^*$ by $\varphi(w_1w_2...w_r)=\varphi(w_1)\varphi(w_2)...\varphi(w_r)$. Substitutions have many interesting qualities, and arise in the mathematical fields of geometry, combinatorics, and dynamics, and also in various fields of physical sciences (notably, the study of quasicrystals). There is a stillunproven conjecture in the study of substitutions, known as the \emph{Coincidence Conjecture}. The Coincidence Conjecture states that every substitution that fulfills the criteria for being of \emph{Pisot type} (see Definition \ref{def:pisot} achieves the following combinatorial condition: for every distinct $i,j\in\cA$, there exist integers $k,n$ such that $\varphi^n(i)$ and $\varphi^n(j)$ have the same $k$th letter, and the prefixes of length $k1$ of $\varphi^n(i)$ and $\varphi^n(j)$ are the same up to the reordering of the letters. This coincidence condition has important implications for the properties of the substitution, and so the Coincidence Conjecture is of particular significance in the study of substitutions. The Coincidence Conjecture has been proven for substitutions defined on twoletter alphabets, but is still open for alphabets of higher order. This paper attempts to do several things. First, it provides a thorough survey of the background of the study of substitutions, providing a good starting reference for further study of literature in this area. It also expands on the background, providing several new results. Finally, it explores several computational aspects of the Coincidence Conjecture that have not been previously investigated, resulting in some interesting new observations. 