16
$\begingroup$

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.:

Improve this question
$\endgroup$
3

4 Answers 4

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ p-group/p-regular, wikipedia $\endgroup$
    – vzn
    Sep 18, 2013 at 20:45
  • $\begingroup$ @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. $\endgroup$
    – J.-E. Pin
    Sep 18, 2013 at 20:53
  • $\begingroup$ oops, thx for clarification! p-groups? by the way, similarly, do you know of any CS connection for infinite groups? $\endgroup$
    – vzn
    Sep 18, 2013 at 23:15
  • $\begingroup$ @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. $\endgroup$
    – J.-E. Pin
    Sep 19, 2013 at 6:02
  • $\begingroup$ @vzn I also added automatic groups in my answer. There is a large literature on these groups. $\endgroup$
    – J.-E. Pin
    Sep 19, 2013 at 6:10
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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/…. $\endgroup$
    – Sasho Nikolov
    Apr 12, 2014 at 1:47
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Thomas Klimpel
    Apr 3, 2016 at 21:21
  • $\begingroup$ @ThomasKlimpel Could you say more about the relationship with PIT? $\endgroup$
    – Martin Berger
    Apr 4, 2016 at 8:48
  • $\begingroup$ 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. $\endgroup$
    – Thomas Klimpel
    Apr 4, 2016 at 9:45
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Dec 29, 2016 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.