Finiteness problem for automaton groups over a binary alphabet is almost decidable (Q6930242)

Let \(X\) be a finite non-empty alphabet. A \textit{finite invertible automaton} \(A\) over \(X\) is a tuple \(A=(X,Q,\varphi,\lambda)\), where \(Q\) is a finite set of states, \N\(\varphi:Q\times X\rightarrow Q\) and \(\lambda:Q\times X\rightarrow X\) are maps and the map \(\pi_q:x\in X\mapsto \pi_q(x)=\lambda(q,x)\in X\) is a bijection for every \(q\in Q\). The \textit{inverse automaton} \(A^{-1}=(X,Q^{-1},\varphi,\lambda)\) is defined with a set of states \(Q^{-1}=\{q^{-1}\,:\, q\in Q\}\) and maps \(\varphi\) and \(\lambda\) defined by \N\[\N\varphi(q^{-1},x)=\varphi(q,y)^{-1}\quad\text{and}\quad\lambda(q^{-1},x)=y,\N\]\Nwhere \(y\) is a letter such that \(\lambda(q,y)=x\). In particular, for every \(q\in Q\), \(f_{q^{-1}}\) is the inverse of \(f_q\). Combining \(A\) and \(A^{-1}\), we can extend the domains of the maps \(\varphi\) and \(\lambda\) to \((Q\cup Q^{-1})^\ast\times X^\ast\) (here \(\,^\ast\) denotes the set of all words in the given alphabet). Two elements \(w_1,w_2\in(Q\cup Q^{-1})^\ast\) are equivalent (we write \(w_1\cong w_2\)) if \(\lambda(w_1,w)=\lambda(w_2,w)\) for all \(w\in X^\ast\). The permutation group \(G(A)\) generated by the set \(\{f_q\,:\, q\in Q\}\) is the associated \textit{automaton group}.\N\NThe \textit{nucleus} of \(A\) is defined as \N\[\N\mathcal N(A)=\bigcap_{n\geq0}\big\{\varphi(q,q)\,:\, q\in Q,\,w\in X^\ast,\, |w|\geq n\big\}.\N\]\NMoreover, \(A\) is called \textit{state-liftable} if \(\mathcal N(A)=A\) and there exists a map \N\[\Nr:X^2\times X\rightarrow (Q\cup Q^{-1})^\ast\N\]\Nsuch that \(\lambda\big(r(p),x_1x_2\big)=yx_2\) and \(\varphi\big(r(p),x_1x_2\big)\simeq\Lambda\) for all pairs \(p=(x_1x_2,y)\in X^2\times X\) (note that \(X^n\) is the set of all words over \(X\) of length at most \(n\) and that \(\Lambda\) denotes the empty word).\N\NThe two main results of the paper are the following infiniteness criteria for~\(G(A)\):\N\N\begin{itemize}\N\N\item If \(A\) is a state-liftable automaton for which there exists \(\omega\in(Q\cup Q^{-1})^\ast\) and \(x\in X\) such that \(x\neq \varphi(w,x)\cong\Lambda\), then \(G(A)\) is infinite.\N\N\item If \(A\) is an invertible automaton over the binary alphabet for which \(\mathcal N(A)=A\) and there exist \(q_1,q_2\in Q\), \(x_1,x_2\in X\) such that \(\varphi(q_1,x_1)=\varphi(q_2,x_2)\) and \(\pi_{q_1}\neq\pi_{q_2}\), then \(G(A)\) is infinite.\N\N\end{itemize}\N\NIt is also shown that there exists an algorithm that decides infiniteness of the automaton group (over a binary alphabet) for almost all automata.