Teoremas de puente para teoría de grupos y lenguajes formales.

13

¿Hay alguna forma natural o notable de relacionar o vincular grupos matemáticos y lenguajes formales de CS o algún otro concepto central de CS, por ejemplo, máquinas de Turing?

Estoy buscando referencias / aplicaciones. Sin embargo, tenga en cuenta que conozco el vínculo entre los semigrupos y los lenguajes CS (es decir, a través de autómatas finitos ). (¿Esta literatura sobre semiautomas alguna vez se refiere a "autómatas grupales"?)

Hace muchos años, vi un artículo que podría acercarse, que convierte las tablas de transición de TM en una operación binaria, posiblemente a veces un grupo en algunos casos, posiblemente basado en algún tipo de simetría en la tabla de estado de TM. No exploró eso en particular, pero tampoco lo descartó.

Además, en particular, con respecto al gran cuerpo de investigación matemática sobre clasificación de grupos finitos , ¿tiene o podría tener algún significado o interpretación en TCS? ¿Cuál es la visión de "lente algorítmica" de este edificio masivo de investigación matemática? ¿Qué está "diciendo" sobre una posible estructura oculta en la computación?

Esta pregunta se inspira en parte en algunas otras notas, por ejemplo:

vzn
fuente
1
La pregunta sobre Mathoverflow está relacionada con esta pregunta.
scaaahu
Estoy pensando en mover mi pregunta ¿Cuál es la clase de idiomas aceptados por los DFA cuyos monoides de transición son grupos de permutación transitiva? en Math.SE hasta aquí dependiendo del resultado de esta pregunta.
scaaahu
@scaaahu Creo que la teoría de grupos encaja mucho mejor que la combinatoria . También piense que debe mover su pregunta sobre Matemáticas aquí en cualquier caso.
Raphael

Respuestas:

12

Permítanme responder primero a su pregunta: ¿La literatura sobre semiautomas alguna vez analiza "autómatas grupales"? . La respuesta es sí. En su libro (Autómatas, idiomas y máquinas. Vol. B, Academic Press), S. Eilenberg describió los idiomas regulares reconocidos por grupos conmutativos finitos y grupos . Se conocen resultados similares para grupos nilpotentes finitos, grupos solubles y grupos supersolubles.p

Los grupos finitos también juegan un papel importante en el problema de encontrar un conjunto completo de identidades para expresiones regulares. John Conway propuso un conjunto completo infinito y esta conjetura finalmente fue probada por D. Krob. Hay un número finito de identidades "básicas", más una identidad para cada grupo simple finito . Vea mi respuesta a esta pregunta para referencias.

En la dirección opuesta, la teoría de autómatas finitos conduce a una prueba elemental de resultados básicos en la teoría de grupos combinatorios, como la fórmula de Schreier. Basado en el artículo seminal de Stallings, Topología de gráficos finitos .

También en la dirección opuesta, los grupos automáticos se definen en términos de autómatas finitos.

Los grupos profinitas también juegan un papel importante en la teoría de autómatas. Un ejemplo es la caracterización de los lenguajes regulares reconocidos por autómatas reversibles de transición con posiblemente varios estados iniciales y finales.

Para una conexión muy agradable entre lenguajes, grupos y lógica sin contexto, vea el artículo de David E. Muller y Paul E. Schupp, Lenguajes, grupos sin contexto, teoría de los fines, lógica de segundo orden, problemas de mosaico, celular autómatas y sistemas de adición de vectores .

J.-E. Alfiler
fuente
p-group / p-regular , wikipedia
vzn
p
¡Uy, gracias por aclarar! grupos p ? por cierto, de manera similar, ¿conoce alguna conexión CS para grupos infinitos?
vzn
@vzn El artículo de Muller y Schupp trata sobre grupos infinitos. Dio a luz a la noción de grupo sin contexto . Del mismo modo, los grupos profinitas libres son infinitos.
J.-E.
@vzn También agregué grupos automáticos en mi respuesta. Existe una gran literatura sobre estos grupos.
J.-E.
11

1S5A5 Circuitos de protección con grupos de Miles y Viola (2012).

Con respecto a la clasificación de los grupos simples finitos, que yo recuerde, se usa implícitamente en algunos algoritmos para el isomorfismo de grupo, un problema relacionado con el isomorfismo de grafos.

Yuval Filmus
fuente
1
Yuval, creo que se refiere al problema del isomorfismo grupal (con los grupos dados como tablas de multiplicación) para grupos simples finitos. Según la clasificación, tienen un grupo generador de tamaño como máximo dos, lo que da un algoritmo muy fácil: mathoverflow.net/questions/59213/… .
Sasho Nikolov
10

g1,...,gma1=b1,...,an=bnx,y{g1,...,gm}{sol1,...,solmetro}X=y .

Hay muchos resultados profundos que dan condiciones para las clases de grupos que tienen problemas de palabras solucionables. También es interesante estudiar la complejidad de decidir problemas de palabras (para clases de grupos que tienen un problema de palabras decidible), ver, por ejemplo, aquí .

Martin Berger
fuente
Esta complejidad de decidir problemas de palabras era exactamente lo que estaba buscando. Parece establecer una correspondencia interesante (¿equivalencia?) Con las pruebas de identidad polinomiales probabilísticas, si se utiliza una representación de programa en línea recta para el grupo libre (que también parece aplicarse a las pruebas de identidad para el monoide libre).
Thomas Klimpel
@ThomasKlimpel ¿Podría decir más sobre la relación con PIT?
Martin Berger
Bueno, resulta que en realidad es PIT de polígonos constantes (es decir, sin variables) sobre Z. Esta relación proviene de la multiplicación de las matrices enteras de 2x2, porque esa multiplicación se puede hacer completamente en representación de programa en línea recta. Pero incluso para el PIT de polígonos constantes sobre Z, actualmente no existe una desrandomización conocida, por lo que puede ser una buena relación.
Thomas Klimpel
-1

Con Google, encontré el artículo Monoides profínicos relativamente gratuitos: una introducción y ejemplos, en Semigroups, Formal Languages ​​and Groups por Jorge Almeida (traducción al inglés en Journal of Mathematical Sciences , 144 (2): 3881–3903, 2007) en este tema.

xuan-gottfried Yang
fuente
44
Bienvenido al sitio! Edité tu publicación para incluir una cita completa del artículo, en caso de que el enlace desaparezca. Sería útil si pudiera dar un poco más de información sobre cómo este documento responde a la pregunta.
David Richerby