Zastosowania struktur algebraicznych w informatyce teoretycznej

Jestem praktykiem oprogramowania i piszę ankietę na temat struktur algebraicznych do badań osobistych i staram się przedstawić przykłady wykorzystania tych struktur w informatyce teoretycznej (oraz, w mniejszym stopniu, w innych dziedzinach informatyki) .

W ramach teorii grup natknąłem się na monoidy syntaktyczne dla języków formalnych oraz monoidy śledzenia i historii dla obliczeń równoległych / współbieżnych.

Z punktu widzenia teorii pierścieni natknąłem się na ramy semeryzacji do przetwarzania grafów i analizy składniowej.

Muszę jeszcze znaleźć zastosowanie struktur algebraicznych z teorii modułów w moich badaniach (i chciałbym).

Zakładam, że są dalsze przykłady i po prostu nie szukam odpowiedniego miejsca, aby je znaleźć.

Jakie są inne przykłady struktur algebraicznych z wyżej wymienionych domen, które są powszechnie spotykane w informatyce teoretycznej (i innych dziedzinach informatycznych)? Alternatywnie, jakie czasopisma lub inne zasoby możesz polecić na te tematy?

Mam wrażenie, że ogólnie rzecz biorąc, tradycyjna algebra jest zbyt specyficzna, aby można ją było zastosować w informatyce. Informatycy albo stosują słabsze (a zatem bardziej ogólne) struktury, albo uogólniają tradycyjne struktury, aby dopasować je do swoich potrzeb. Używamy również teorii kategorii dużo, których matematycy nie uważają za część algebry, ale nie rozumiemy, dlaczego nie. Regimentacja tradycyjnej matematyki na „algebrze” i „topologii” uważamy za osobne gałęzie niewygodne, a nawet bezcelowe, ponieważ algebra jest generalnie pierwszego rzędu, podczas gdy topologia ma szansę zajmować się aspektami wyższego rzędu. Tak więc struktury używane w informatyce mają mieszaną algebrę i topologię. W rzeczywistości powiedziałbym, że mają tendencję raczej do topologii niż algebry. Regimentacja rozumowania do „algebry” i „logiki” jest kolejnym bezcelowym podziałem z naszego punktu widzenia, ponieważ algebra zajmuje się właściwościami równań, podczas gdy logika dotyczy również wszystkich innych rodzajów właściwości.

Wracając do pytania, półgrupy i monoidy są dość intensywnie wykorzystywane w teorii automatów. Eilenberg napisał 2-tomową kolekcję , z których drugą jest prawie całkowicie algebra. Powiedziano mi, że planował cztery tomy, ale jego wiek nie pozwolił na zakończenie projektu. Jean-Eric Pin ma zmodernizowaną wersję wielu tych treści w książce online . Automaty to „moduły monoidów” (zwane również „działaniami monoidów” lub „aktami”), które są na odpowiednim poziomie ogólności dla informatyki. Tradycyjne moduły pierścieniowe są prawdopodobnie zbyt specyficzne.

Teoria kratowa była główną siłą w rozwoju semantyki denotacyjnej. Topologia została zmieszana z teorią sieci, gdy informatycy wspólnie z matematykami opracowali ciągłe sieci, a następnie uogólnili je na dziedziny . Powiedziałbym, że teoria domen jest własną matematyką informatyków, o której tradycyjna matematyka nie ma wiedzy.

Algebra uniwersalna służy do definiowania specyfikacji algebraicznych typów danych . Po dotarciu na miejsce informatyści od razu zauważyli potrzebę zajęcia się bardziej ogólnymi właściwościami: równaniami warunkowymi (zwanymi także klauzulami równania Rogu) i właściwościami logicznymi pierwszego rzędu, wciąż wykorzystując te same idee algebry uniwersalnej. Jak można zauważyć, algebra łączy się teraz w teorię modeli.

Teoria kategorii jest podstawą teorii typów. Ponieważ informatycy wciąż wymyślają nowe struktury do radzenia sobie z różnymi zjawiskami obliczeniowymi, teoria kategorii stanowi bardzo pocieszające ramy, w których można umieścić wszystkie te pomysły. Używamy również struktur, które są włączane przez teorię kategorii, które nie istnieją w „tradycyjnej” matematyce, takich jak kategorie funktorów. Również algebra wraca do obrazu z kategorycznego punktu widzenia w zastosowaniu monad i algebraicznych teorii efektów . Koalgebry , które są dualistami algebry, również znajdują wiele zastosowań.

Istnieje więc szerokie zastosowanie „algebry” w informatyce, ale nie jest to rodzaj algebry spotykany w tradycyjnych podręcznikach algebry.

$a : X \rightarrow Y$$a : X \rightarrow Y$$b : Y \to Z$$ab : X \to Z$$n \times n$macierze mają operację mnożenia, co czyni je monoidami. Jednak macierzy (gdzie i mogą być różne) tworzą kategorię. Monoidy są zatem szczególnymi przypadkami kategorii, które mają jeden typ. Pierścienie są specjalnymi przypadkami kategorii dodatków, które mają jeden typ. Moduły to specjalne przypadki funktorów, w których kategorie źródłowa i docelowa mają jeden typ. Wkrótce. Teorią kategorii jest algebra maszynowa, której typy sprawiają, że jest ona nieskończenie bardziej przydatna niż algebra tradycyjna.m $m \times n$$m$$n$

Moim ulubionym zastosowaniem teorii grup w TCS jest twierdzenie Barringtona. Ekspozycję tego twierdzenia można znaleźć na blogu złożoności , a ekspozycję Barringtona w sekcji komentarzy tego wpisu.

Grupy, pierścienie, pola i moduły są wszędzie w topologii obliczeniowej. Zobacz zwłaszcza pracę Carlssona i Zomorodiana [np. 1 ] na temat (wielowymiarowej) trwałej homologii, która dotyczy stopniowanych modułów w stosunku do głównych idealnych domen.

Oto bardzo ładne, praktyczne zastosowanie: algorytm do obliczania połączeń grafów (z FOCS2011 ). Aby obliczyć łączność s-> t wykresu, autorzy podają algorytm, który przypisuje losowe wektory z wpisami wyciągniętymi z pola skończonego do zewnętrznych krawędzi od s, a następnie konstruuje podobne wektory dla wszystkich krawędzi na wykresie przez losowe kombinacje liniowe i wreszcie odkryć łączność, obliczając rangę powstałych wektorów przypisanych do krawędzi t.

Kraty i punkty stałe są podstawą analizy i weryfikacji programu. Chociaż rzadko wykorzystywane są zaawansowane wyniki z teorii sieci, ponieważ zajmujemy się zagadnieniami algorytmicznymi, takimi jak obliczanie i aproksymowanie punktów stałych, podczas gdy badania nad teorią sieci koncentrują się na innych zagadnieniach (połączenia z topologią, teorią dualności itp.). Wstępne abstrakcyjne prace interpretacyjne używają podstawowej teorii sieci. Praca Roberto Giacobazzi i jego współpracowników wykorzystuje bardziej zaawansowane wyniki.

W obliczeniach rozproszonych uzyskano sławną rodzinę wyników niemożliwości przy użyciu metod topologii algebraicznej (patrz praca Maurice'a Herlihy i Nira Shavita).

[Edycja: patrz zastosowania topologii w informatyce .]

Algebra uniwersalna jest ważnym narzędziem w badaniu złożoności problemów związanych z satysfakcją z ograniczeń.

Na przykład, hipoteza dychotomii stwierdza, że ​​z grubsza mówiąc, problem satysfakcji z ograniczeń w skończonej dziedzinie jest albo NP-zupełny, albo rozwiązany w czasie wielomianowym. Zauważ, że według twierdzenia Ladnera występują problemy w NP, które nie są w P i nie są NP-kompletne, chyba że P = NP, więc przypuszczenie mówi, że CSP są specjalni w dychotomii, której nie mają większe klasy złożoności. Dostarczyłby również wyjaśnienia, dlaczego większość problemów, które napotykamy w praktyce, można zaklasyfikować jako NP-zupełne lub w P.

Dychotomie udowodniono w kilku szczególnych przypadkach, np. CSP w domenie binarnej (Schaefer) i CSP w domenie trójskładnikowej (Bulatov), ​​a homomorfizmy w niekierowanych grafach (Hell and Nesetril). Ale ogólna sprawa jest dość otwarta. Jedną z głównych linii ataku jest algebra uniwersalna. Z grubsza (i zdecydowanie nie jestem w tym ekspertem!) Definiuje się polimorfizm CSP jako funkcję w dziedzinie CSP, która pozostawia wszystkie spełnione ograniczenia, jeśli zostaną zastosowane do każdej zmiennej. Zbiór polimorfizmów CSP w pewnym sensie oddaje jego złożoność. Na przykład, jeśli CSP A dopuszcza wszystkie polimorfizmy CSP B, wówczas A jest czasem wielomianowym redukowalnym do B. Zbiór polimorfizmów tworzy algebrę, której struktura wydaje się pomocna w opracowywaniu algorytmów / pokazywaniu redukcji. Na przykład, jeśli algebra polimorfizmu w CSP jest idempotentna i przyjmuje typ jednoargumentowy, wówczas CSP jest NP-kompletny. Idempotencja jest uproszczonym założeniem, które można czynić mniej więcej bez utraty ogólności. Wykazanie, że CSP, którego algebra jest idempotentna i nie przyznaje, że typ jednoargumentowy może zostać rozwiązany w czasie wielomianowym, udowodni hipotezę dychotomii.

Zobacz ankietę Bułatowa: http://www.springerlink.com/content/a553847g6h673k05/ .

Oto dwie aplikacje z innej części TCS.

Semirowania są używane do modelowania adnotacji w bazach danych (szczególnie tych potrzebnych do pochodzenia), a często także do struktur wyceny w celu spełnienia wartościowego ograniczenia. W obu tych aplikacjach poszczególne wartości muszą być łączone ze sobą w sposób, który w naturalny sposób prowadzi do struktury semieralnej, ze skojarzeniem i jedną operacją semieralną rozłożoną na drugą. Jeśli chodzi o zapytanie dotyczące modułów, żaden monoid nie ma odwrotności w tych aplikacjach.

• Todd J. Green, Grigoris Karvounarakis i Val Tannen. Semirings proweniencyjne , strąki 2007 DOI: 10,1145 / 1265530,1265535 ( preprint )
• Stefano Bistarelli, Ugo Montanari i Francesca Rossi. Zadowolenie i optymalizacja ograniczeń opartych na semestrach, JACM 1997. doi: 10.1145 / 256303.256306 ( preprint )

Pierścienie, moduły i odmiany algebraiczne są używane w korekcji błędów i, bardziej ogólnie, w teorii kodowania.

W szczególności istnieje abstrakcyjny schemat korekcji błędów (kody algebraiczno-geometryczne), który uogólnia kody Reeda-Solomona i kody chińskiego reszty. Schemat polega na tym, aby zabrać wiadomości z pierścienia R i zakodować je, przyjmując jego modulo wiele różnych ideałów w R. Przy pewnych założeniach dotyczących R można udowodnić, że robi to porządny kod korygujący błędy.

W świecie dekodowania list niedawny artykuł Guruswamiego podaje liniowo-algebraiczną metodę dekodowania listy fałdowanych kodów Reeda-Solomona, która ma dobrą właściwość polegającą na tym, że wszystkie wiadomości kandydujące znajdują się w niskowymiarowej podprzestrzeni afinicznej przestrzeni wiadomości . Można budować zestawy wymijające podprzestrzeni , zestawy, które są prawie tak duże jak cała przestrzeń, ale mają małe przecięcie z każdą niskopłaszczyznową podprzestrzenią afiniczną. Jeśli ograniczy się wiadomości do wysyłania z zestawu wymijającego podprzestrzeń w przestrzeni wiadomości, wówczas schemat Guruswami daje algorytm, który gwarantuje niezłą wielkość listy. Jak dotąd jedyną wyraźną konstrukcję zestawów wymijających podprzestrzeń podali Dvir i Lovett w nadchodzącym artykule STOC, Zestawy podprzestrzenne wymijające i zbuduj zestaw, biorąc konkretną odmianę afiniczną (i zabierając ze sobą jej kartezjański produkt).

Sprawdź teorię Ramseya - zasadniczo znaczące uogólnienie zasady szufladki, która leży u podstaw wielu automatów i teorii języka formalnego (a raczej powiedzieć, że szufladka jest najprostszym przypadkiem teorii Ramseya). Mówi w zasadzie, że nawet wysoce nieuporządkowane struktury muszą koniecznie zawierać dużo porządku, jeśli są wystarczająco duże. Na przykład, poza zasadą szufladki, zauważ, że jeśli weźmiesz jakieś sześć osób, to albo trzy z nich się znają, albo trzy z nich się nie znają.

Ten artykuł wygląda na dobre miejsce do nawiązania kontaktów z informatyką, ale możesz znaleźć w Google więcej. Jest bardziej kombinatoryczny niż algebraiczny w swojej podstawowej naturze, ale ma wiele zastosowań w algebrze i teoretycznej CS.

A także sprawdź historię wynalazcy Franka Ramseya - naprawdę niezwykłego polimatarza, który wniósł fundamentalny, wręcz rewolucyjny wkład w ekonomię i filozofię, a także matematykę. Pomyśl! W rzeczywistości oryginalne twierdzenie Ramseya, będące podstawą teorii Ramseya, było zwykłym lematem w pracy o większym celu w logice matematycznej.

Analizowanie każdego problemu z dużą symetrią jest ułatwione dzięki zastosowaniu teorii grup. Przykładem może być znalezienie algorytmów dla rzeczy takich jak kostka rubika. Chociaż nie znam szczegółów, jestem pewien, że udowodnienie, że liczba Boga wynosi 20, wymagało poważnego teoretycznego przycięcia grupy. W innym kontekście praktyczne rozwiązania dla problemu izomorfizmu grafów, takie jak nauty, wykorzystują grupę automorfizmów na wykresie.

$\mathbb{Z}_p$

W programowaniu funkcjonalnej, najbardziej ogólne i eleganckie abstrakcje dla problemów są często algebraiczne (lub kategoria-teoretyczne) w charakterze: monoids, semirings , funktory, monady F-algebry F-coalgebras itp Niektóre klasyczne wyniki (np Yoneda lemma) zdarza się mieć zawartość obliczeniową i narzędzie.

Istnieje również teoria typów homotopii, która interpretuje teorię typów w (niejako) algebraicznym otoczeniu topologicznym.

Niedawno badamy (patrz nasz artykuł na stronie Springerlink: formalne ujednolicenie szeregów podejść do eksploracji częstych zestawów przedmiotów ) próbę ujednolicenia próby wydobycia wzorców (popularny przypadek eksploracji danych) za pomocą formalnych szeregów i ważonych automatów. Narzędzia te są oparte na odwzorowaniach między monoidami i strukturami semiring.