Teorema jembatan untuk teori grup dan bahasa formal

Apakah ada cara alami atau terkenal untuk menghubungkan atau menautkan kelompok matematika dan bahasa formal CS atau konsep inti CS lainnya misalnya mesin Turing?

Saya mencari referensi / aplikasi. Namun perhatikan bahwa saya mengetahui tautan antara semigroup dan bahasa CS (yaitu via finata automata ). (Apakah literatur tentang semiautomata ini pernah melihat "group-automata"?)

Saya telah melihat satu makalah bertahun-tahun yang lalu yang mungkin datang dekat, yang mengubah tabel transisi TM menjadi operasi biner, mungkin kadang-kadang kelompok dalam beberapa kasus, mungkin didasarkan pada semacam simetri dalam tabel negara TM. Itu tidak mengeksplorasi itu secara khusus, tetapi juga tidak mengesampingkannya.

Juga, khususnya, mengenai kumpulan besar penelitian matematika tentang klasifikasi kelompok terbatas , apakah atau dapatkah itu memiliki makna atau interpretasi dalam TCS? Apa pandangan "lensa algoritmik" dari bangunan besar penelitian matematika ini? Apa yang "dikatakan" tentang kemungkinan struktur tersembunyi dalam perhitungan?

Pertanyaan ini sebagian terinspirasi oleh beberapa catatan lain misalnya:

• Penggunaan struktur aljabar di TCS

• RJ Lipton pada teorema Gromov

Biarkan saya menjawab pertanyaan Anda dulu: Apakah literatur tentang semiautomata pernah melihat "group-automata"? . Jawabannya iya. Dalam bukunya (Automata, bahasa, dan mesin. Vol. B, Academic Press), S. Eilenberg memberikan karakterisasi dari bahasa-bahasa reguler yang dikenali oleh kelompok komutatif hingga dan grup- . Hasil serupa diketahui untuk kelompok nilpoten terbatas, kelompok terlarut dan kelompok supersoluble.$p$

Kelompok terbatas juga memainkan peran penting dalam masalah menemukan serangkaian identitas lengkap untuk ekspresi reguler. Set lengkap yang tak terbatas diusulkan oleh John Conway dan dugaan ini akhirnya dibuktikan oleh D. Krob. Ada sejumlah terbatas identitas "dasar", ditambah identitas untuk setiap grup sederhana hingga . Lihat jawaban saya untuk pertanyaan ini untuk referensi.

Dalam arah yang berlawanan, teori automata terbatas mengarah pada bukti dasar hasil dasar pada teori kelompok kombinatorial, seperti rumus Schreier. Berdasarkan kertas mani Stallings, Topology of Finite Graphs .

Juga di arah yang berlawanan, grup otomatis didefinisikan dalam hal automata terbatas.

Kelompok-kelompok yang tak terbatas juga memainkan peran penting dalam teori automata. Contohnya adalah karakterisasi bahasa reguler yang dikenali oleh automata transisi-reversibel dengan kemungkinan beberapa kondisi awal dan akhir.

Untuk koneksi yang sangat bagus antara bahasa bebas konteks, grup dan logika, lihat artikel oleh David E. Muller dan Paul E. Schupp, bahasa bebas konteks, grup, teori tujuan akhir, logika tingkat kedua, masalah ubin, seluler automata, dan sistem penambahan vektor .

$^1$$S_5$$A_5$

Mengenai klasifikasi grup sederhana hingga, sejauh yang saya ingat itu secara implisit digunakan dalam beberapa algoritma untuk grup isomorfisma, masalah yang berkaitan dengan grafik isomorfisme.

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

Ada banyak hasil mendalam yang memberikan kondisi bagi kelas-kelas kelompok yang memiliki masalah kata yang dapat dipecahkan. Menarik juga untuk mempelajari kerumitan dalam memutuskan masalah kata (untuk kelas kelompok yang memiliki masalah kata yang dapat ditentukan), lihat misalnya di sini .

Dengan Google, saya menemukan makalah monoid tak terbatas yang relatif bebas: sebuah pengantar dan contoh, dalam Semigroup, Bahasa Resmi dan Grup oleh Jorge Almeida (Terjemahan bahasa Inggris di Journal of Mathematics Sciences , 144 (2): 3881-3903, 2007) di Subjek ini.