Automata defined by group presentations.

Question

I apologise if this question is ill-formed or too broad. It's just for fun. I've thrown in the soft question tag for good measure.

Let $G=\langle X\mid R\rangle$ be a group. What can be said in relation to $G$ about the automaton $\mathcal{A}(G)$ whose accepted language over the alphabet $X\cup X^{-1}$ is (the set of relators) $R$?

It's a long time since I've done anything with formal languages and automata, so please forgive me as I just point out one obvious feature as my input.

If $G$ is finitely presented, then $\mathcal{A}(G)$ is a finite state automaton.

Answer 1

In general, I think that you really want to talk about the automata accepted by the elements of $\langle\langle R\rangle\rangle\leq F(X)$ (where $\langle\langle R\rangle\rangle$ denotes the normal closure of the set $R$). This is because we can change the relators really easily, but this subgroup is somehow more rigid. The elements of this subgroup form a language, often referred to as "the word problem", and of course languages and automata are related.

Theorem. (Muller-Schupp, 1983) A finitely generated group $G=\langle X; R\rangle$ has context free word problem (that is, elements of $\langle\langle R\rangle\rangle$ form a context free language) if and only if the group $G$ is virtually free.

That is, the automata $\mathcal{A}$ which accepts precisely the set of elements $\langle\langle R\rangle\rangle\leq F(X)$ is a pushdown automata if and only if the group contains a free subgroup of finite index.

This theorem is super-important. It says that we can gain algebraic information about groups by understanding their languages of word problems, and vice-versa. It plays a similar strategic role to Gromov's theorem on groups of polynomial growth, which says that we can gain algebraic information about groups by understanding their coarse geometries, and vice-versa.

Answer 2

Let $G = \langle X \mid R \rangle$ be a finitely generated group and let $W(G)$ be the set of words of $(X \cup X^{-1})^*$ representing the empty word. Here are a few results.

Theorem [1]. $W(G)$ is regular if and only if $G$ is finite.

Theorem [9, 4]. The following conditions are equivalent:

1. $W(G)$ is context-free,
2. $W(G)$ is deterministic context-free,
3. $G$ is virtually free.

Theorem [5, 6]. The following conditions are equivalent:

1. $W(G)$ is one-counter,
2. $W(G)$ is deterministic one-counter,
3. $G$ is virtually cyclic.

Theorem [3]. $W(G)$ is recursive if and only if $G$ embeds in a simple subgroup of a finitely presented group.

Theorem [7]. $W(G)$ is recursively enumerable if and only if $G$ embeds in a finitely presented group.

More results can be found in the survey article [10], in R. Thomas' lectures Formal languages and group theory and Word problems of groups, formal languages and decidability or in Part III of the book [8].

[1] A. V. Anisimov, The group languages, Kibernetika 4 (1971) 18–24.

[2] A. V. Anisimov, Certain algorithmic questions for groups and context-free languages, Kibernetika 8 (1972) 4–11.

[3] W. W. Boone and G. Higman, An algebraic characterization of groups with soluble word problem, J. Australian Math. Soc. 18 (1974) 41–53.

[4] M. J. Dunwoody, The accessibility of finitely presented groups, Invent. Math. 81 (1985) 449–457.

[5] T. Herbst, On a subclass of context-free groups, Theor. Informatics and Applications 25 (1991) 255–272.

[6] T. Herbst and R. M. Thomas, Group presentations, formal languages and characterizations of one-counter groups, Theoret. Comput. Sci. 112 (1993) 187–213.

[7] G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. Ser. A 262 (1961), 455–475.

[8] D. F. Holt, S. Rees and C. E. Röver, Groups, languages and automata, London Mathematical Society Student Texts 88, Cambridge University Press, Cambridge, 2017.

[9] D. E. Muller and P. E. Schupp, Groups, the theory of ends and context-free languages, J. Comput. System Sci. 26 (1983) 295–310.

[10] I. A. Stewart and R. M. Thomas, Formal Languages and the Word Problem for Groups, Groups St. Andrews 1997 in Bath, II, London Math. Soc. Lecture Note Ser. 261, Cambridge Univ. Press, Cambridge} (1999) 689-700.