Zwykłe języki z teoretycznego punktu widzenia kategorii

Zauważyłem, że zwykłe języki nad alfabetem można naturalnie traktować jako zestaw, a nawet sieć. Co więcej, konkatenacja wraz z pustym językiem określa ścisłą strukturę monoidalną w tej kategorii, która rozkłada się na złączenia (nie jestem pewien, czy się spotykają). Czy to przydatny konstrukt w teorii lub praktyce zwykłych języków? Czy można znaleźć jakieś fajne połączenia, np. Czy możemy zdefiniować gwiazdę Kleene jako jedną?$\Sigma$$\epsilon$

To jest kopia pytania zadanego na kursie Kompilatory w Coursera: https://class.coursera.org/compilers/forum/thread?thread_id=311

Wiele zrobiono, stosując teorię kategorii do zwykłych języków i automatów. Punktem wyjścia są ostatnie artykuły:

• Bialgebraiczny przegląd deterministycznych automatów, wyrażeń regularnych i języków autorstwa Barta Jacobsa
• Bialgebraiczne podejście do automatów i teorii języka formalnego Jamesa Worthingtona.

W pierwszym z tych artykułów strukturę wyrażeń regularnych traktuje się algebraicznie, a generowane języki traktuje się jako algebraicznie. Te dwa widoki są zintegrowane w ustawieniu bialgebraicznym. Bialgebra to para algebra-węgielgebra z odpowiednim prawem dystrybucyjnym, przechwytującym wzajemne oddziaływanie między składniowymi terminami (wyrażenia regularne) a zachowaniem obliczeniowym (generowane języki). Podstawą tego artykułu jest algebra i węgielgebra, traktowane w informatyce pod parasolami algebry uniwersalnej i węgielgebra, a nie to, co widzi się w matematyce (grupy itp.).

Drugi artykuł wykorzystuje techniki, które pochodzą z bardziej tradycyjnego matematycznego traktowania algebry (modułów itp.) I carbongebra, ale obawiam się, że nie znam szczegółów.

O ile wiem, nie traktuję gwiazdy Kleene jako dodatku.

Mówiąc bardziej ogólnie, jest dużo pracy nad zastosowaniem teorii kategorii do automatów zamiast wyrażeń regularnych. Próbka tej pracy obejmuje:

• Bloom SL; Sabadini N .; Matryce, maszyny i zachowania Walters RFC . Applied Categorical Structures, tom 4, nr 4, grudzień 1996, s. 343–360 (18)

• Michael A. Arbib, Ernest G. Manes: Kategoryzacyjne spojrzenie na automaty i systemy. Teoria kategorii zastosowana do obliczeń i kontroli 1974: 51-64

• MA Arbib i EG Manes. Maszyny dodatkowe, maszyny zachowania państwowego i dualność . Journal of Pure and Applied Algebra, 6: 313-344, 1975.

• MA Arbib i EG Manes. Maszyny w kategorii . Journal of Pure and Applied Algebra, 19: 9-20, 1980.
• Książka Jirí Adámka i Very Trnková Automata i algebry w kategoriach , jak wskazano w komentarzu .

Wreszcie, praca nad teoriami iteracyjnymi, teorie iteracyjne : logika równikowa procesów iteracyjnych Stephena L. Blooma i Zoltána Ésika, która koncentruje się na iteracji (np. Gwiazda Kleene), ale z bardziej ogólnej perspektywy, gdzie zwykłe języki są po prostu jedna rzecz wchodzi w zakres teorii.

Właściwie myślę, że szukasz algebry Kleene. Zobacz klasyczny artykuł Dextera Kozen'a. Daje aksjatyzację gwiazdy Kleene. Zakładam, że to pierwszy krok, który Cię interesuje.

Twierdzenie o kompletności dla algeb Kleene i algebry regularnych zdarzeń. Informacje i obliczenia, 110 (2): 366–390, maj 1994 r.

W tym artykule nie stosuje się teorii kategorii, ale daje ona równomierną aksjatyzację algeb Kleene, których struktura obejmuje strukturę zwykłych języków. Algebry Kleene z testami można postrzegać jako rozszerzenie wyrażeń regularnych do modelowania prostych programów z pętlami i warunkami (ale bez przypisań). To rozszerzenie jest przydatne do wnioskowania o tak prostych programach w sposób czysto algebraiczny.

O koalgebraicznej teorii algebry Kleene'a z testami. Raport techniczny. Uniwersytet Cornell, marzec 2008 r.

Jak zaobserwujesz, zwykłe języki tworzą algebrę logiczną o dodatkowej strukturze. Struktura ta została zbadana z punktu widzenia dualności kamienia przez Nicka Pippengera.

Zwykłe języki i kamienna dualność . Nicholas Pippenger. Theory Computing Systems, 1997: 121-134.

Podejście dualności do rozpoznawania języka było ostatnio w centrum uwagi i zostało zastosowane w celu uzyskania nowych wyników w zakresie rozpoznawania języka.

Dualizm i teoria równań języków regularnych. M. Gehrke, S. Grigorieff, J.-E. Kołek.

Patrzenie na świat za pomocą okularów teorii kategorii nazywa się kategoryzacją . Czasami daje naprawdę ładne i zaskakujące wyniki. Fizycy zaczęli mówić, że myślenie o grupie jako jednoelementowej gropoidie robi naprawdę dużą różnicę . Zaczynam zdawać sobie sprawę, że myślenie o monoidzie jako kategorii jednoskładnikowej również upraszcza wiele rzeczy. (Na przykład akcja monoidu jest wtedy funktorem w zestawie . Takie rzeczy tworzą kategorie zamknięte i kartezjańskie. Toposy. Mają więc rachunek lambda i intuicyjną logikę!)

Chcesz kategoryzować zwykłe języki. Nie wiem, czy zostało to zrobione, czy zrobione i uznane za nieciekawe. Nie widziałem nic na ten temat. Jednak struktura algebraiczna języków regularnych, algebry Kleene, jest wystarczająco interesująca. Jest na nich mnóstwo literatury. Ale moim zdaniem teoria zwykłych języków i automatów skończonych cierpi z powodu przedwczesnego przywiązania do skończoności. (Grupy skończone są interesujące i ważne, ale nie chcesz, aby definicja „grupy” od początku zobowiązała się do skończoności.) Przydałoby się zatem wyrzucenie skończoności i bardziej ogólne badanie struktur.

Najciekawsze obecnie prowadzone prace dotyczą struktur zwanych bimonoidami lokalizacyjnymi zdefiniowanymi przez Hoare'a. Stwierdzono, że współbieżne algebry Kleene są ich przykładem . Bimonoidy lokalizacji i współbieżność to aktywny kierunek badań.