Cayley automata (Q685452)

For a finite symmetrized set \(X\) of abstract generators of a group \(G\) and their inverses, the \textit{Cayley graph} of \(G\) w.r.t. \(X\) is the regular digraph of degree \(| X|\) with vertex set \(G\) in which every \(g\in G\) is connected to each product \(gx\), \(x\in X\), by an edge labeled \(x\). A (0-\textit{pebble}) \textit{Cayley automaton} \(M=(Q,\Sigma,X,\delta,q_ 0,F)\) is a generalized finite-state automaton that admits as inputs Cayley graphs of a fixed degree (corresponding to a fixed set \(X\) of abstract generators and their inverses) whose vertices are labeled from a two-element alphabet \(\Sigma=\{0,1\}\) such that exactly one vertex (corresponding to the group identity) is marked by 1, and all other vertices are marked 0. The automaton starts in an initial state \(q_ 0\in Q\) with the (read-only) input head positioned on the marked initial vertex of the input Cayley graph. In each step, it changes its state and moves along one edge in the Cayley graph according to the (non-deterministic) transition function \(\delta:Q\times\Sigma\to 2^{Q\times X}\). The \textit{language} recognized by \(M\) is the set of labeled Cayley graphs for which \(M\) reaches one of the accepting states \(F\subseteq Q\). The paper discusses properties of languages accepted by (special classes of) Cayley automata. By reduction from the word problem of group theory, it is shown that the emptiness decision problem for the subclass of halting deterministic Cayley automata is unsolvable. It is also proved that the language accepted by a deterministic halting Cayley automaton is equational, i.e. characterized by a finite set of equations and inequalities of words over the generators \(X\). Furthermore, the author shows that nondeterministic Cayley automata with at least two generators \((| X|\geq 4)\) are more powerful than deterministic ones.