Chciałbym napisać ankietę na temat zastosowań topologii w informatyce. Planuję opisać historię pomysłów topologicznych w dziedzinie informatyki, a także zwrócić uwagę na kilka aktualnych osiągnięć. Byłoby niezwykle pomocne, gdyby ktokolwiek mógł udzielić informacji na temat któregokolwiek z poniższych pytań.
Czy są jakieś prace lub notatki opisujące chronologię wykorzystania topologii w informatyce?
Jakie są najważniejsze zastosowania wyników w Topologii do informatyki?
Jakie są najciekawsze obszary bieżącej pracy, które wykorzystują topologię, aby uzyskać wgląd w obliczenia?
Dzięki!
Odpowiedzi:
Osobiście uważam, że najciekawszym zastosowaniem topologii była praca wykonana przez Herlihy i Shavit. Wykorzystali topologię algebraiczną do scharakteryzowania asynchronicznego obliczenia rozproszonego i dali nowe dowody ważnych znanych wyników oraz znokautowali szereg długotrwałych otwartych problemów. Wygrali Godel 2004 nagrodę za tę pracę.
„Topologiczna struktura obliczeń asynchronicznych” Maurice Herlihy i Nir Shavit, Journal of the ACM, t. 46 (1999), 858–923,
źródło
Topologia jest tak dojrzałą dyscypliną z różnorodnymi subpólami, w tym geometryczną, algebraiczną, metryczną, zestawem punktów i (samorzutną) bezcelową topologią. Informatyka jest również dość szeroka i ma wiele podobszarów matematycznych, więc oczekiwałbym wielu zastosowań pomysłów topologicznych w CS. Marshall Stone powiedział „zawsze topologizuj”, a informatycy z wymaganym doświadczeniem często to robią. Dość bla. Kilka przykładów.
Te przykłady to nie tylko trudne problemy CS rozwiązane przez topologię. Czasami pojęcie topologiczne bardzo dobrze przenosi się na ustawienie CS lub daje podstawę dla podobszaru CS.
Twierdzenie o zwartości logiki zdań jest konsekwencją twierdzenia Tychonoffa. Zwartość w logice pierwszego rzędu jest zwykle udowodniona inaczej. Zwartość jest ważnym narzędziem w klasycznej teorii modeli.
Twierdzenie Stone'a o algebrach boolowskich dotyczy modeli logiki zdań, algebry boolowskiej i niektórych przestrzeni topologicznych. Wyniki dualności typu kamiennego uzyskano dla struktur stosowanych w logice algebraicznej i semantyce języka programowania.
Nick Pippenger zastosował twierdzenie Stone'a do algebry boolowskiej zwykłych języków i wykorzystał topologię do udowodnienia kilku faktów na temat zwykłych języków. Zobacz komentarz Jean-Erica Pin'a, aby zapoznać się z najnowszymi pracami nad topologią w teorii języków.
W metodach formalnych istnieją pojęcia własności bezpieczeństwa i żywotności. Każda właściwość czasu liniowego może być wyrażona jako przecięcie właściwości bezpieczeństwa i żywotności. Dowód wykorzystuje elementarną topologię.
Martín Escardó opracował algorytmy i napisał programy do wyszukiwania nieskończonych zbiorów. Uważam, że zwartość jest kluczowym składnikiem tej pracy.
Praca polskich topologów (takich jak Kuratowski) dała nam operatory zamknięcia. Operatory zamykania na siatkach są kluczową częścią teorii abstrakcyjnej interpretacji, która leży u podstaw statycznej analizy programu.
Operatory zamknięcia i inne pomysły topologiczne są podstawą morfologii matematycznej.
Pojęcie operatorów wewnętrznych również z polskiej szkoły jest ważne w aksjatyzacji logiki modalnej.
Wiele informatyki opiera się na strukturach graficznych. Niektóre aplikacje wymagają bogatszych pojęć związanych z połączeniami i przepływami niż te zapewniane przez grafy, a topologia jest naturalnym następnym krokiem. To jest moja interpretacja wyższych wymiarów automatów van Glabbeeka w teorii współbieżności i zastosowanie topologii geometrycznej przez Erica Goubaulta do semantyki programów współbieżnych.
Być może największą popularnością cieszy się aplikacja wykorzystująca topologię (początkowo algebraiczną, choć istnieją również inne kombinatoryczne prezentacje) w celu scharakteryzowania niektórych scenariuszy tolerancji błędów w obliczeniach rozproszonych. Oprócz wspomnianego wyżej Herlihy i Shavita, Borowsky i Gafni, a także Saks i Zaharouglou dali dowód za pierwszy taki przełom. Ramy obliczeń asynchronicznych dały więcej takich wyników.
Twierdzenie Brouwera o punkcie stałym dało początek kilku problemom, które badamy. Ostatnio w badaniach nad algorytmiczną teorią gier, klasą złożoności PPAD i klasą złożoności FixP problemów z punktami stałymi.
Twierdzenie Borsuka-Ulama ma kilka zastosowań w grafach i osadzeniach metrycznych. Są one opisane w książce Jiří Matouška.
To skromne wybory na to, co tam jest. Powodzenia!
źródło
Z semantyki denotacyjnej wynikają związki z abstrakcyjną interpretacją oraz analizą i weryfikacją programu.
Obecne badania obejmują zapewnienie semantyki denotacyjnej dla współbieżności i języków kwantowych.
Abramsky i Jung przedstawiają miłą analizę głównych pomysłów: teorii domen .
źródło
Ograniczenia dotyczące liczby połączonych komponentów, a bardziej ogólnie liczb Bettiego, odmian algebraicznych i układów hiperpłaszczyznowych (oraz ich uzupełnień) zastosowano w kilku dolnych granicach obliczeń algebraicznych i drzew decyzyjnych. Aby zobaczyć tylko kilka dużych referencji, zobacz:
W innym, ale nieco pokrewnym stylu, Smale zastosował topologię w dość interesujący sposób (w szczególności kohomologię grupy warkoczy), aby obniżyć granicę złożoności znalezienia korzenia w modelu Blum-Shub-Smale:
źródło
Jest to związane z odpowiedzią Dave'a i teorią domen. Podstawowym argumentem jest tutaj to, że obliczalność jest z natury oparta na lokalnych operacjach i skończonych obserwacjach . Obliczenia można traktować jako dopracowane pojęcie topologii. Najbardziej wyraźnym przykładem jest to, że:
Więcej można znaleźć w książce Klausa Weihraucha „Analiza obliczeniowa”. Możesz także zajrzeć do ładnej książki Stevena Vickersa zatytułowanej „Topologia przez logikę”.
źródło
Dwa inne artykuły, które mogą być istotne dla Twojej ankiety ...
M. Gehrke, S. Grigorieff, J.-E. Pin, Topologiczne podejście do rozpoznawania, ICALP 2010, część II, Uwagi do wykładu z informatyki 6199, Springer Verlag, (2010), 151-162.
M. Gehrke, S. Grigorieff, J.-E. Pin, Dwoistość i teoria równania języków regularnych, Nagroda za najlepszą pracę papierową ICALP 2008, Ścieżka B, ICALP 2008, Część II, Uwagi do wykładu z informatyki 5126, Springer Verlag, (2008), 246-257.
źródło
Nie zapomnij przypuszczenia Knesera i dowodu Kahna / Saksa / Sturtevanta dla przypuszczenia Aandery-Rosenberga-Karpa.
źródło
Nie widziałem wspomnianej pracy Roberta Ghrista , wcześniej w Illinois, ale teraz w U Penn, stosującej topologię do takich rzeczy, jak sieci czujników i robotyka. Oto miły wywiad.
Również bardzo związany z pracą Gunnara Carlssona i in. Nad zastosowaniem topologii do analizy danych .
Być może nie STS / FOCS TCS, ale zdecydowanie informatyka.
źródło
Teorie rozumienia współbieżności i modelowania obliczeń współbieżnych najlepiej zrozumieć topologicznie. Oprócz słynnej pracy Herlihy i Shavita na temat topologicznej struktury obliczeń asynchronicznych wspomnianej we wcześniejszej odpowiedzi - Eric goubault wykonał prace nad modelowaniem współbieżności z geometrią, a praca Pratta nad zastosowaniem przestrzeni Chu do współbieżności w grupie konkurentów Stanforda jest również interesująca chociaż nie znam ich pracy.
źródło
Wszystkie prace rozpoczęte przez Kitaeva nad topologicznym podejściem do odpornego na uszkodzenia komputera kwantowego. Zobacz oryginalny artykuł Kitaeva lub, na przykład, notatki z wykładu Johna Preskilla .
źródło
Nikt jeszcze nie wspomniał o ukierunkowanej topologii algebraicznej , która w rzeczywistości została opracowana w celu zapewnienia odpowiedniego algebraicznego zestawu narzędzi topologicznych do badania współbieżności.
Istnieje również kilka nisko wymiarowych podejść topologicznych do tematów teorii obliczeń, wszystkie dość nowe:
źródło
Niektóre aplikacje do osadzania danych.
Sprawdź tę książkę Matousek: http://kam.mff.cuni.cz/~matousek/akt.html
Sprawdź także następujące dokumenty:
źródło
przeczytaj tę książkę:
Zobacz zarchiwizowaną stronę internetową
źródło
Sprawdź tę książkę, Złożoność obliczeniowa: perspektywa ilościowa, bada rozmiar niektórych klas złożoności przy użyciu narzędzi topologicznych ograniczonych do zasobów.
źródło