Finiteness problem for automaton groups over a binary alphabet is almost decidable
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.
- Automata, dynamical systems, and groups
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- Classification of groups generated by 3-state automata over a 2-letter alphabet
- scientific article; zbMATH DE number 5855532 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- On orbits and the finiteness of bounded automaton groups
- On the finiteness problem for automaton (semi)groups.
- The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
- The finiteness problem for automaton semigroups is undecidable.
This page was built for publication: Finiteness problem for automaton groups over a binary alphabet is almost decidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930242)
