Pont des théorèmes pour la théorie des groupes et les langages formels

13

Existe-t-il un moyen naturel ou notable de relier ou de lier des groupes mathématiques et des langages CS formels ou un autre concept CS fondamental, par exemple les machines de Turing?

Je recherche des références / applications. Notez cependant que je suis conscient du lien entre les semigroupes et les langages CS (notamment via des automates finis ). (Cette littérature sur les semi-automates examine-t-elle jamais les «groupes-automates»?)

Il y a de nombreuses années, j'ai vu un document qui pourrait se rapprocher, qui convertit les tables de transition TM en une opération binaire, peut-être parfois un groupe dans certains cas, peut-être basé sur une sorte de symétrie dans la table d'état TM. Il n'a pas exploré cela en particulier, mais ne l'a pas non plus exclu.

En particulier, en ce qui concerne le vaste corpus de recherches en mathématiques sur la classification des groupes finis , cela a-t-il ou pourrait-il avoir une signification ou une interprétation dans TCS? Quelle est la "lentille algorithmique" de cet édifice massif de la recherche mathématique? Que dit-il d'une éventuelle structure cachée dans le calcul?

Cette question est en partie inspirée par d'autres notes, par exemple:

vzn
la source
1
La question sur Mathoverflow est liée à cette question.
scaaahu
Je pense à déplacer ma question Quelle est la classe de langues acceptée par les DFA dont les monoïdes de transition sont des groupes de permutation transitive? sur Math.SE à ici en fonction du résultat de cette question.
scaaahu
@scaaahu Je pense que la théorie des groupes convient mieux que la combinatoire . Pensez également que vous devriez déplacer votre question sur les mathématiques ici dans tous les cas.
Raphael

Réponses:

12

Permettez-moi d'abord de répondre à votre sous-question: la littérature sur les semi-automates examine-t-elle jamais les «automates de groupe»? . La réponse est oui. Dans son livre (Automates, langages et machines. Vol. B, Academic Press), S. Eilenberg a donné une caractérisation des langages réguliers reconnus par les groupes commutatifs finis et les groupes . Des résultats similaires sont connus pour les groupes nilpotents finis, les groupes solubles et les groupes supersolubles.p

Les groupes finis jouent également un rôle important dans le problème de la recherche d'un ensemble complet d'identités pour les expressions régulières. Un ensemble complet infini a été proposé par John Conway et cette conjecture a finalement été prouvée par D. Krob. Il existe un nombre fini d'identités «de base», plus une identité pour chaque groupe simple fini . Voir ma réponse à cette question pour les références.

Dans la direction opposée, la théorie des automates finis conduit à une preuve élémentaire des résultats de base sur la théorie des groupes combinatoires, comme la formule de Schreier. Basé sur le papier séminal de Stallings Topology of Finite Graphs .

Toujours dans la direction opposée, les groupes automatiques sont définis en termes d'automates finis.

Les groupes de profit jouent également un rôle important dans la théorie des automates. Un exemple est la caractérisation des langages réguliers reconnus par des automates à transition réversible avec éventuellement plusieurs états initial et final.

Pour une très belle connexion entre les langages sans contexte, les groupes et la logique, voir l'article de David E. Muller et Paul E. Schupp, Langages sans contexte, groupes, théorie des fins, logique du second ordre, problèmes de tuilage, cellulaire automates et systèmes d'addition de vecteurs .

J.-E. Épingle
la source
p-group / p-regular , wikipedia
vzn
@vzn Je ne connaissais pas cette terminologie "langages p-réguliers" mais ce sont en fait des langages reconnus par des groupes finis, pas par des groupes finis. p
J.-E.
oups, merci de clarifier! p-groupes ? au fait, de la même manière, connaissez-vous une connexion CS pour des groupes infinis?
vzn
@vzn L'article de Muller et Schupp traite de groupes infinis. Il a donné naissance à la notion de groupe hors contexte . De même, les groupes profins libres sont infinis.
J.-E.
@vzn J'ai également ajouté des groupes automatiques dans ma réponse. Il existe une grande littérature sur ces groupes.
J.-E.
11

1S5A5

En ce qui concerne la classification des groupes simples finis, pour autant que je m'en souvienne, elle est implicitement utilisée dans certains algorithmes d'isomorphisme de groupe, un problème lié à l'isomorphisme des graphes.

Yuval Filmus
la source
1
Yuval, je pense que vous faites référence au problème d'isomorphisme de groupe (avec les groupes donnés sous forme de tables de multiplication) pour les groupes simples finis. Selon la classification, ils ont un groupe électrogène de taille au plus deux, ce qui donne un algorithme très simple: mathoverflow.net/questions/59213/… .
Sasho Nikolov
10

g1,...,gmune1=b1,...,unen=bnX,y{g1,...,gm}{g1,...,gm}X=y

Il existe de nombreux résultats profonds donnant des conditions pour des classes de groupes ayant des problèmes de mots résolubles. Il est également intéressant d'étudier la complexité de la résolution des problèmes de mots (pour les classes de groupes qui ont un problème de mots décidables), voir par exemple ici .

Martin Berger
la source
Cette complexité de décider des problèmes de mots était exactement ce que je cherchais. Il semble établir une correspondance intéressante (équivalence?) Aux tests d'identité polynomiaux probabilistes, si une représentation de programme linéaire est utilisée pour le groupe libre (ce qui semble également s'appliquer aux tests d'identité pour le monoïde libre).
Thomas Klimpel
@ThomasKlimpel Pourriez-vous en dire plus sur la relation avec PIT?
Martin Berger
Eh bien, il s'avère qu'il s'agit en fait de PIT de polygones constants (c'est-à-dire sans variables) sur Z. Cette relation provient de la multiplication des matrices entières 2x2, car cette multipication peut être entièrement réalisée en représentation de programme en ligne droite. Mais même pour le PIT de polygones constants sur Z, il n'existe actuellement aucune dérandomisation connue, donc cela peut être une bonne relation néanmoins.
Thomas Klimpel
-1

Avec Google, j'ai trouvé l'article Reloid free profinite monoids: an introduction and exemples, in Semigroups, Formal Languages ​​and Groups de Jorge Almeida (traduction anglaise dans Journal of Mathematical Sciences , 144 (2): 3881–3903, 2007) sur ce sujet.

xuan-gottfried Yang
la source
4
Bienvenue sur le site! J'ai modifié votre message pour inclure une citation complète au journal, au cas où le lien mourrait. Il serait utile de donner un peu plus d'informations sur la façon dont ce document répond à la question.
David Richerby