Twierdzenia mostkowe dla teorii grup i języków formalnych

Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga?

Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS (mianowicie za pośrednictwem automatów skończonych ). (Czy ta literatura na temat półautomatów dotyczy kiedykolwiek „automatów grupowych”?)

Wiele lat temu widziałem jeden artykuł, który może się zbliżyć, który przekształca tabele przejścia TM w operację binarną, w niektórych przypadkach czasami grupę, prawdopodobnie opartą na pewnej symetrii w tabeli stanów TM. W szczególności nie zbadał tego, ale też nie wykluczył.

Również, w szczególności, jeśli chodzi o obszerne badania matematyczne dotyczące klasyfikacji grup skończonych , czy może ono mieć jakiekolwiek znaczenie lub interpretację w TCS? Jaki jest widok „soczewki algorytmicznej” tego ogromnego gmachu badań matematycznych? Co to „mówi” o możliwej ukrytej strukturze w obliczeniach?

To pytanie jest częściowo inspirowane innymi notatkami, np .:

• Zastosowanie struktur algebraicznych w TCS

• RJ Lipton o twierdzeniu Gromova

Pozwól mi najpierw odpowiedzieć na twoje pytanie: czy literatura na temat półautomatów kiedykolwiek patrzy na „automaty grupowe”? . Odpowiedź brzmi tak. W swojej książce (Automaty, języki i maszyny. Vol. B, Academic Press) S. Eilenberg przedstawił charakterystykę zwykłych języków rozpoznawanych przez skończone grupy przemienne i grupy . Podobne wyniki są znane dla skończonych grup nilpotentnych, grup rozpuszczalnych i grup superspuszczalnych.$p$

Grupy skończone odgrywają również ważną rolę w problemie znalezienia pełnego zestawu tożsamości dla wyrażeń regularnych. Nieskończony pełny zestaw został zaproponowany przez Johna Conwaya i ta hipoteza została ostatecznie udowodniona przez D. Kroba. Istnieje skończona liczba „podstawowych” tożsamości oraz tożsamość dla każdej skończonej prostej grupy . Zobacz moją odpowiedź na to pytanie, aby uzyskać odniesienia.

W przeciwnym kierunku teoria automatów skończonych prowadzi do elementarnego dowodu podstawowych wyników teorii kombinatorycznej grup, takich jak formuła Schreiera. Na podstawie przełomowego artykułu Stallingsa Topology of Finite Graphs .

Również w przeciwnym kierunku grupy automatyczne są zdefiniowane w kategoriach automatów skończonych.

Grupy profinite odgrywają również ważną rolę w teorii automatów. Przykładem jest charakterystyka zwykłych języków rozpoznawanych przez automatyczne odwracalne przejścia z prawdopodobnie kilkoma stanami początkowymi i końcowymi.

Aby uzyskać bardzo miłe połączenie między bezkontekstowymi językami, grupami i logiką, zobacz artykuł Davida E. Mullera i Paula E. Schuppa, Języki bezkontekstowe, grupy, teoria celów, logika drugiego rzędu, problemy z kafelkami, komórkowe automaty i systemy dodawania wektorów .

$^1$$S_5$$A_5$

Jeśli chodzi o klasyfikację skończonych prostych grup, o ile pamiętam, jest ona domyślnie stosowana w niektórych algorytmach dla izomorfizmu grupowego, problem związany z izomorfizmem grafowym.

$g_1, ..., g_m$$a_1 = b_1, ..., a_n = b_n$$x, y \in \{g_1, ..., g_m\}^*$$\{g_1, ..., g_m\}$$x = y$

Istnieje wiele głębokich wyników dających warunki dla klas grup mających rozwiązywalne problemy słowne. Interesujące jest również zbadanie złożoności rozwiązywania problemów słownych (dla klas grup, które mają problem ze słowami rozstrzygalnymi), patrz np . Tutaj .

W Google znalazłem artykuł Relatywnie wolne profinite monoidy: wprowadzenie i przykłady, w półgrupach, językach formalnych i grupach autorstwa Jorge Almeidy (angielskie tłumaczenie w Journal of Mathematical Sciences , 144 (2): 3881–3903, 2007) na ten temat.