Do czego służą kraty?

Wikipedia mówi :

Kompletne sieci pojawiają się w wielu zastosowaniach w matematyce i informatyce

Czy odnosi się to tylko do faktu, że standardowa algebra boolowska wykorzystywana w obliczeniach jest kompletną siecią? Czy coś zyskujemy dzięki pracy na abstrakcyjnym poziomie sieci, a nie logice logicznej?

Wyszukiwarka Google nie znajduje wiele na ten temat, ale prawdopodobnie używam niewłaściwych słów kluczowych.

Zobacz na przykład tę książkę: Lattice Theory with Applications, Vijay K. Garg , która zaczyna się następująco:

Teoria częściowego uporządkowania i sieci odgrywa teraz ważną rolę w wielu dyscyplinach informatyki i inżynierii. Na przykład mają zastosowania w obliczeniach rozproszonych (zegary wektorowe, globalne wykrywanie predykatów), teorii współbieżności (pomsety, sieci występowania), semantyce języka programowania (semantyka stała) i eksploracji danych (analiza koncepcji). Są również przydatne w innych dyscyplinach matematyki, takich jak kombinatoryka, teoria liczb i teoria grup. W tej książce przedstawiam ważne wyniki teorii częściowego porządku wraz z ich zastosowaniami w informatyce. Preferencja książki dotyczy aspektów obliczeniowych teorii sieci (algorytmów) i aplikacji (zwłaszcza systemów rozproszonych).

Książka wydaje się nie wspominać o teorii rekurencji (teorii zbiorów obliczalnych), ale z artykułu Wikipedii na temat teorii obliczeń widzimy:

Kiedy Post zdefiniował pojęcie zestawu prostego jako zestawu z nieskończonym dopełnieniem niezawierającym żadnego zestawu nieskończonego, zaczął badać strukturę zestawów rekurencyjnie możliwych do wyliczenia. Ta sieć stała się dobrze zbadaną strukturą. Zbiory rekurencyjne mogą być zdefiniowane w tej strukturze przez podstawowy wynik, że zbiór jest rekurencyjny wtedy i tylko wtedy, gdy zbiór i jego dopełnienie są rekurencyjnie policzalne. Nieskończone zestawy ponownie mają zawsze nieskończone rekurencyjne podzestawy; ale z drugiej strony istnieją proste zestawy, ale nie mają skończonego rekurencyjnego supersetu. Post (1944) wprowadził już zestawy hipersproste i hipershipersymalne; później skonstruowano zestawy maksymalne, które są zestawami tak, że każdy zestaw ponownie jest albo skończonym wariantem danego zestawu maksymalnego, albo jest skończony. Poczta' pierwotną motywacją w badaniu tej sieci było znalezienie takiego pojęcia strukturalnego, że każdy zestaw spełniający tę właściwość nie jest ani w stopniu Turinga zbiorów rekurencyjnych, ani w stopniu Turinga problemu zatrzymania. Post nie znalazł takiej właściwości, a rozwiązanie jego problemu zastosowało metody priorytetowe; Harrington i Soare (1991) znaleźli w końcu taką właściwość.

Więcej informacji można znaleźć na blogu Teoria krat dla programistów i naukowców niebędących informatykami .

Odniesienia podane przez Pål GD są rzeczywiście bardzo odpowiednie. Zamiast tego skupmy się na drobnym problemie ubocznym w tej odpowiedzi. Czytałem już jakiś czas na siatkach i zacząłem się zastanawiać, czy pojęcie semilattice nie byłoby bardziej odpowiednie dla aplikacji. Możesz sprzeciwić się temu, że kompletna pół-krata jest automatycznie również siatką, ale homomorfizmy i podstruktury (tj. Podsieci i podzespoły) są różne.

Po raz pierwszy zetknąłem się z (pół-) sieciami podczas studiowania półgrup, jako przemiennych idempotentnych półgrup. Potem pomyślałem o związku między strukturami hierarchicznymi a sieciami i zauważyłem, że drzewo jest naturalnie również semilattice. Potem znalazłem sieci w kontekście bezpieczeństwa i analizy programu i zawsze wydawało mi się, że struktura półksiężyca była naprawdę ważną częścią, a sieć została po prostu wzięta, ponieważ można ją uzyskać „za darmo”. Nawet w przypadku algebry Heytinga istnieje asymetria między koniunkcją a rozłączeniem, co sugeruje mi, że asymetryczny model semilattice może zapewnić tutaj więcej wglądu niż symetryczny model sieci.

bardzo ważnym, ale nie tak znanym przypadkiem - jest dobrze znany wśród teoretyków, ale nie tak dobrze znany w sensie uczenia się studentów - o zastosowaniu sieci kratowej jest udowodnienie super wielomianowych dolnych granic wielkości obwodów monotonicznych komputerowa klika, za którą Razborow zdobył nagrodę Nevanlinna . oryginalna konstrukcja jest jednak bardzo techniczna, a późniejsze konstrukcje, np. Berg / Ulfberg, upraszczają szkielet bez odniesienia do krat.

więc w tym przypadku teoria sieci została wykorzystana jako podstawa do odkrycia oryginalnego dowodu, ale później sformułowania zwykle nie odwoływały się do niej bezpośrednio jako uproszczenia koncepcyjnego.

więc tak kraty można uznać za bardziej egzotyczny obiekt matematyczny [Razborov mówił gdzie indziej o swoim stylu stosowania zaawansowanej matematyki do CS], który może odpowiadać innemu bardziej „konkretnemu” obiektowi w CS, w tym przypadku są to „bramki aproksymacyjne” tzn. bramki logiczne w obwodach, które dają odpowiedzi „w przybliżeniu poprawne” i których sieć stanowi rodzaj „struktury indukcyjnej” do konwersji między dokładnym obwodem w niedokładny, przybliżony obwód.

Od tamtej pory znalazłem bezpłatny artykuł Zamówione zestawy i Kompletne kraty: elementarz informatyki dla innych zainteresowanych czytelników.

Regularne opisy krawędzi i powiązane struktury tworzą sieć dystrybucyjną (patrz na przykład tutaj ). Można to wykorzystać do wydajnego przeszukiwania przestrzeni wszystkich regularnych etykiet krawędzi dla danego wykresu (patrz tutaj ). Jako aplikacja możesz określić, czy mapę można narysować jako kartogram z określonym przypisaniem obszaru do twarzy.

Co zaskakujące (przynajmniej dla mnie) kryptografia . Sprawdź to, pozwala na nowe ataki znanych kryptosystemów i daje nadzieję na kryptografię obliczeniową.