Zastosowania teorii mnogości, teorii porządkowej, nieskończonej kombinatoryki i ogólnej topologii w informatyce?

Jestem matematykiem zainteresowanym teorią zbiorów, teorią porządkową, nieskończoną kombinatoryką i topologią ogólną.

Czy są jakieś zastosowania dla tych przedmiotów w informatyce? Szukałem trochę i znalazłem wiele zastosowań (oczywiście) do teorii grafów skończonych, topologii skończonej, topologii niskowymiarowej, topologii geometrycznej itp.

Szukam jednak zastosowań nieskończonych obiektów tych podmiotów, tj. Drzew nieskończonych ( na przykład drzew Aronszajna ), nieskończonej topologii itp.

Jakieś pomysły?

Dziękuję Ci!!

Jednym z głównych zastosowań topologii w semantyce jest topologiczne podejście do obliczalności.

Podstawowa koncepcja topologii obliczalności wynika z obserwacji, że zakończenie i nieterminacja nie są symetryczne. Można zaobserwować, czy program czarnej skrzynki się kończy (wystarczy poczekać wystarczająco długo), ale nie można zaobserwować, czy się nie kończy (ponieważ nigdy nie możesz być pewien, że nie czekałeś wystarczająco długo, aby się zakończył). Odpowiada to wyposażeniu zestawu dwóch punktów {HALT, LOOP} w topologię Sierpińskiego, gdzie $\emptyset, \{HALT\}, and \{HALT, LOOP\}$są otwarte zestawy. Zatem możemy zasadniczo zrównać „otwarty zestaw” z „właściwością obliczalną”. Jedną niespodzianką tego podejścia do tradycyjnych topologów jest centralna rola przestrzeni spoza Hausdorffa. Wynika to z faktu, że można w zasadzie dokonać następujących identyfikacji

$$\begin{matrix} \mathbf{Computability} & \mathbf{Topology}\\ \mbox{Type} & \mbox{Space} \\ \mbox{Computable function} & \mbox{Continuous function} \\ \mbox{Decidable set} & \mbox{Clopen set} \\ \mbox{Semi-decidable set} & \mbox{Open set} \\ \mbox{Set with semidecidable complement} & \mbox{Closed set} \\ \mbox{Set with decidable equality} & \mbox{Discrete space} \\ \mbox{Set with semidecidable equality} & \mbox{Hausdorff space} \\ \mbox{Exhaustively searchable set} & \mbox{Compact space} \\ \end{matrix}$$

Dwa dobre badania tych pomysłów to Topologia MB Smyth w Handbook of Logic in Computer Science oraz Topologia syntetyczna Martina Escardo typów danych i klasycznych przestrzeni .

Metody seologiczne również odgrywają ważną rolę w semantyce współbieżności, ale wiem o tym znacznie mniej.

Nagroda Gödela z 2004 roku została podzielona między gazety:

• Topologiczna struktura obliczeń asynchronicznych .
  Autorzy: Maurice Herlihy i Nir Shavit, Journal of the ACM, t. 46 (1999), 858–923
• Umowa k-set bez czekania jest niemożliwa: topologia wiedzy publicznej .
  Autorzy: Michael Saks i Fotios Zaharoglou, SIAM J. on Computing, t. 29 (2000), 1449-1483.

Cytaty z nagrody Gödela 2004 roku:

Oba artykuły stanowią jeden z najważniejszych przełomów w teorii przetwarzania rozproszonego.

Odkrycie topologicznej natury obliczeń rozproszonych zapewnia nowe spojrzenie na ten obszar i stanowi jeden z najbardziej uderzających przykładów, być może we wszystkich zastosowanej matematyce, zastosowania struktur topologicznych do kwantyfikacji naturalnych zjawisk obliczeniowych.

---

Temat powiązany: Zastosowania topologii w informatyce

Zachowanie się układu reaktywnego jest często modelowane przy użyciu struktur nieskończonych (drzewa obliczeniowe o nieskończonym kształcie i nieskończone), a ich właściwości doczesne (właściwości bezpieczeństwa i żywotności) zostały również scharakteryzowane przy użyciu topologii.

Definiowanie żywotności Alpern i Schneider

Bezpieczeństwo i żywotność w czasie rozgałęzienia Manolios i in. glin.