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ą?ϵ
To jest kopia pytania zadanego na kursie Kompilatory w Coursera: https://class.coursera.org/compilers/forum/thread?thread_id=311
fl.formal-languages
regular-language
ct.category-theory
Aleksiej Averchenko
źródło
źródło
Odpowiedzi:
Wiele zrobiono, stosując teorię kategorii do zwykłych języków i automatów. Punktem wyjścia są ostatnie artykuły:
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.
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.
źródło
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.
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.
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.
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.
źródło
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ń.
źródło