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

13

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

— vzn
źródło

1

Pytanie na Mathoverflow jest związana z tym pytaniem.

— scaaahu,

Zastanawiam się nad przeniesieniem pytania Jaka klasa języków jest akceptowana przez DFA, których monoidy przejściowe to przechodnie grupy permutacyjne? na Math.SE tutaj w zależności od wyniku tego pytania.

— scaaahu,

@ scaaahu Myślę, że teoria grupowa pasuje znacznie lepiej niż kombinatoryka . Pomyśl też, że w każdym razie powinieneś przenieść tutaj swoje pytanie dotyczące matematyki .

— Raphael

12

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 .

— J.-E. Kołek
źródło

p-group / p-regular , wikipedia

— od

p

$p$

Ups, dzięki za wyjaśnienie! grupy p ? tak przy okazji, czy znasz jakieś połączenie CS dla nieskończonych grup?

— vzn

@vzn Artykuł Mullera i Schuppa dotyczy nieskończonych grup. Powstało pojęcie grupy bezkontekstowej . Podobnie, wolne grupy profinite są nieskończone.

— J.-E.

@vzn W odpowiedzi dodałem również grupy automatyczne. Istnieje duża literatura na temat tych grup.

— J.-E.

11

$^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.

— Yuval Filmus
źródło

1

Yuval, myślę, że odnosisz się do problemu izomorfizmu grupowego (z grupami podanymi w postaci tabliczek mnożenia) dla skończonych prostych grup. Przez klasyfikacji, mają generatora wielkości co najwyżej dwa, co daje bardzo prosty algorytm: mathoverflow.net/questions/59213/... .

— Sasho Nikolov

10

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

— Martin Berger
źródło

Ta złożoność rozwiązywania problemów z słowami była dokładnie tym, czego szukałem. Wydaje się, że ustanawia interesującą zgodność (równoważność?) Z probabilistycznym wielomianowym testowaniem tożsamości, jeśli dla wolnej grupy stosowana jest reprezentacja programu w linii prostej (co wydaje się również mieć zastosowanie do testowania tożsamości dla wolnego monoidu).

— Thomas Klimpel,

@ThomasKlimpel Czy możesz powiedzieć coś więcej o związku z PIT?

— Martin Berger,

Okazuje się, że tak naprawdę jest to PIT stałych wielokątów (tzn. Bez zmiennych) w stosunku do Z. Zależność ta wynika z mnożenia macierzy całkowitych 2x2, ponieważ mnożenia można dokonać całkowicie w postaci reprezentacji programu w linii prostej. Ale nawet w przypadku PIT stałych wielokątów nad Z nie ma obecnie znanej derandomizacji, więc może to być miły związek.

— Thomas Klimpel

-1

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.

— Xuan-Gottfried Yang
źródło

4

Witamy na stronie! Zredagowałem twój post, aby dołączyć pełne cytowanie do artykułu, na wypadek gdyby link umarł. Przydałoby się trochę więcej informacji na temat tego, jak ten artykuł odpowiada na pytanie.

— David Richerby