Cayley automata

DOI10.1016/0304-3975(93)90231-HMaRDI QIDQ685452zbMATH OpenOpenAlexFDO

Publication date 17 October 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90231-h

Cayley automata Cayley graphs equational languages word problem

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Cayley automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685452)