Title: Word problems in Elliott monoids,
Abstract: Algorithmic issues concerning Elliott local semigroups are seldom considered
in the literature, although these combinatorial structures completely classify
AF algebras. In general, the addition operation of an Elliott local semigroup
is {\it partial}, but for every AF algebra $\mathfrak B$ whose Murray-von
Neumann order of projections is a lattice, this operation is uniquely
extendible to the addition of an involutive monoid $E(\mathfrak B)$. Let
$\mathfrak M_1$ be the Farey AF algebra introduced by the present author in
1988 and rediscovered by F. Boca in 2008. The freeness properties of the
involutive monoid $E(\mathfrak M_1)$ yield a natural word problem for every AF
algebra $\mathfrak B$ with singly generated $E(\mathfrak B)$, because
$\mathfrak B$ is automatically a quotient of $\mathfrak M_1$. Given two
formulas $\phi$ and $\psi$ in the language of involutive monoids, the problem
asks to decide whether $\phi$ and $\psi$ code the same equivalence of
projections of $\mathfrak B$. This mimics the classical definition of the word
problem of a group presented by generators and relations. We show that the word
problem of $\mathfrak M_1$ is solvable in polynomial time, and so is the word
problem of the Behnke-Leptin algebras $\mathcal A_{n,k}$, and of the
Effros-Shen algebras $\mathfrak F_{\theta}$, for $\theta\in [0,1]\setminus
\mathbb Q$ a real algebraic number, or $\theta = 1/e$. We construct a quotient
of $\mathfrak M_1$ having a Gödel incomplete word problem, and show that no
primitive quotient of $\mathfrak M_1$ is Gödel incomplete.