Zwykłe języki z teoretycznego punktu widzenia kategorii

21

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

Aleksiej Averchenko
źródło
4
Wystarczy wskazać, że link wymaga zalogowania się na stronie internetowej coursea.
Dave Clarke
1
Jaka jest częściowa kolejność, która zamienia zwykłe języki w zestawy? czy jest to tylko właściwość podzbioru?
Suresh Venkat
@Suresh Tak, coś mi brakuje?
Aleksiej Averchenko
1
Nie. Chciałem tylko zrozumieć, czy istnieje coś bardziej specyficznego w strukturze językowej
Suresh Venkat
@Suresh Z pewnością nie jestem tak mądry ani wykształcony jak ludzie, do których odwołuje się Dave Clarke, więc widziałem tylko najbardziej oczywistą rzecz :)
Alexei Averchenko

Odpowiedzi:

18

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:

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.

Dave Clarke
źródło
2
W przypadku automatów jest także books.google.co.uk/…
Radu GRIGore
1
Niestety termin „algebra” jest nadużywany. Istnieje znaczenie „algebry” jako ogólnej struktury algebraicznej, która jest stosowana w algebrze uniwersalnej, algebrach funktorowych i algebrach monad. Artykuł Bart Jacobs mówi o nich. Istnieje bardziej szczegółowa struktura zwana „ algebrą ” zdefiniowaną w teorii pierścienia / modułu. Pismo Jamesa Worthingtona zajmuje się nimi. Moim zdaniem praca Worthingtona jest o wiele bardziej interesująca, ale myślę, że dopiero zaczęliśmy tutaj zarysowywać powierzchnię.
Uday Reddy,
Link do strony non-paywall do artykułu Barta: repository.ubn.ru.nl/handle/2066/36207
Turion
12

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.

Vijay D.
źródło
1
A konkretnie o niektórych klasycznych kombinacjach
algeb
4

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

Uday Reddy
źródło