# Bridge theorems for group theory and formal languages

Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines?

I am looking for references/applications. However note that I am aware of the link between semigroups and CS languages (namely via finite automata). (Does this literature on semiautomata ever look at "group-automata"?)

I have seen one paper many years ago that might come close, that converts TM transition tables into a binary operation, possibly sometimes a group in some cases, conceivably based on some kind of symmetry in the TM state table. It didn't explore that in particular, but also didn't rule it out.

Also, in particular, regarding the large body of math research on classification of finite groups, does or could it have any meaning or interpretation in TCS? What is the "algorithmic lens" view of this massive edifice of mathematical research? What is it "saying" about a possible hidden structure in computation?

This question is partly inspired by some other notes e.g.:

Let me first answer your subquestion: Does the literature on semiautomata ever look at "group-automata"?. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite nilpotent groups, soluble groups and supersoluble groups.

Finite groups also play an important role in the problem of finding a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob. There is a finite number of "basic" identities, plus an identity for each finite simple group. See my answer to this question for references.

In the opposite direction, finite automata theory lead to an elementary proof of basic results on combinatorial group theory, like the Schreier formula. Based on Stallings's seminal paper Topology of Finite Graphs.

Also in the opposite direction, automatic groups are defined in terms of finite automata.

Profinite groups also play an important role in automata theory. An example is the characterization of the regular languages recognized by transition-reversible automata with possibly several initial and final states.

For a very nice connection between context-free languages, groups and logic, see the article by David E. Muller and Paul E. Schupp, Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems.

• p-group/p-regular, wikipedia – vzn Sep 18 '13 at 20:45
• @vzn I didn't know this terminology "p-regular languages" but they are in fact languages recognized by finite groups, not by finite $p$-groups. – J.-E. Pin Sep 18 '13 at 20:53
• oops, thx for clarification! p-groups? by the way, similarly, do you know of any CS connection for infinite groups? – vzn Sep 18 '13 at 23:15
• @vzn The paper by Muller and Schupp deals with infinite groups. It gave birth to the notion of context-free group. Similarly, free profinite groups are infinite. – J.-E. Pin Sep 19 '13 at 6:02
• @vzn I also added automatic groups in my answer. There is a large literature on these groups. – J.-E. Pin Sep 19 '13 at 6:10

Barrington's famous theorem reduces computation in NC$^1$ to computing iterated products in the group $S_5$ (or $A_5$, or indeed any non-solvable group). There is also a connection to leakage-resistant computation, in Shielding Circuits with Groups by Miles and Viola (2012).

Regarding the classification of the finite simple groups, as far as I remember it is implicitly used in some algorithms for group isomorphism, a problem related to graph isomorphism.

• Yuval, I think what you refer to is the group isomorphism problem (with the groups given as multiplication tables) for finite simple groups. By the classification, they have a generator set of size at most two, which gives a very easy algorithm: mathoverflow.net/questions/59213/…. – Sasho Nikolov Apr 12 '14 at 1:47

A famous area of study in the theory of group presentations is the word problem for groups. A group presentation is given by a bunch of generators $g_1, ..., g_m$ and a bunch of equations $a_1 = b_1, ..., a_n = b_n$ that the generated group needs to satisfy. Now given two words $x, y \in \{g_1, ..., g_m\}^*$, i.e. two strings over the alphabet $\{g_1, ..., g_m\}$, it makes sense to ask if $x = y$ holds in the generated group. This is the word problem. Can we decide the word problem mechanically? This was a long-standing open problem, solved negatively in 1955: there is a finitely generated (in fact, a finitely presented) group G such that the word problem for G is undecidable. However, for many classes of groups the word problem is decidable, e.g. finite groups and braid groups.

There are many deep results giving conditions for classes of groups having solvable word problems. It is also interesting to study the complexity of deciding word problems (for classes of groups that have a decidable word problem), see e.g. here.

• This complexity of deciding word problems was exactly what I was looking for. It seems to establish an interesting correspondence (equivalence?) to probabilistic polynomial identity testing, if a straight-line program representation is used for the free group (which seems also apply to identity testing for the free monoid). – Thomas Klimpel Apr 3 '16 at 21:21
• @ThomasKlimpel Could you say more about the relationship with PIT? – Martin Berger Apr 4 '16 at 8:48
• Well, it turns out it is actually PIT of constant polygons (i.e. no variables) over Z. This relationship comes from the multiplication of the 2x2 integer matrices, because that multipication can be done entirely in straight-line program representation. But even for PIT of constant polygons over Z, there exists currently no known derandomization, so it may be a nice relationship nevertheless. – Thomas Klimpel Apr 4 '16 at 9:45

With Google, I found the paper Relatively free profinite monoids: an introduction and ex- amples, in Semigroups, Formal Languages and Groups by Jorge Almeida (English translation in Journal of Mathematical Sciences, 144(2):3881–3903, 2007) on this subject.

• Welcome to the site! I edited your post to include a full citation to the paper, in case the link dies. It would be helpful if you could give a little more information about how this paper answers the question. – David Richerby Dec 29 '16 at 22:18