Czy jakieś znane CCC są zamknięte w ramach probabilistycznej operacji powerdomain?

Odpowiednio, czy istnieje znana semantyka denotacyjna dla probabilistycznych funkcjonalnych języków programowania wyższego rzędu? Konkretnie, czy istnieje model domenowy czystego nietypowego -kalkultu rozszerzony o symetryczną operację losowego wyboru binarnego.$\lambda$

Motywacja

Kartezjańskie zamknięte kategorie zapewniają semantykę wyższego rzędu -calculi. Probabilistyczne powerdomains zapewniają semantykę programom stochastycznym. CCC zamknięty w ramach probabilistycznej operacji powerdomain zapewni semantykę stochastycznemu funkcjonalnemu językowi programowania wyższego rzędu.$\lambda$

Powiązana praca

Tix, Keimel i Plotkin (2004) [1] przedstawiają nowoczesne konstrukcje operacji powerdomain dolnej, górnej i wypukłej, ale zauważcie, że

Nadal pozostaje otwartym problemem, czy istnieje kartezjańska zamknięta kategoria domen ciągłych, która jest zamknięta w konstrukcji probabilistycznych domen władzy.

Mislove (2013) [2,3] podaje semantykę ciągłych zmiennych losowych w języku pierwszego rzędu, ale zauważa, że

Mimo że probabilistyczna domena mocy pozostawia CCC ukierunkowanych kompletnych zestawów (w skrócie dcpos) i niezmiennych ciągłych map Scotta, nie istnieje zamknięta kartezjańska kategoria domen - dcpos, które spełniają zwykłe założenie przybliżenia - o którym wiadomo, że jest niezmienne ten konstrukt. Najbardziej znane jest to, że kategoria domen spójnych jest niezmienna pod monadą wyboru probabilistycznego [4], ale ta kategoria nie jest zamknięta kartezjańsko.

Bibliografia

1. Regina Tix, Klaus Keimel i Gordon Plotkin (2004) „Domeny semantyczne do łączenia prawdopodobieństwa i niedeterminizmu” .
2. Michael Mislove (2013) „Anatomia domeny ciągłych zmiennych losowych I”
3. Michael Mislove (2013) „Anatomia domeny ciągłych zmiennych losowych II”
4. Jung, A. i R. Tix (1998) „Kłopotliwa probabilistyczna domena władzy”

Poniżej znajduje się rozszerzony komentarz, nie odpowiada na twoje pytanie w kategoriach, które mu postawiłeś, ale daje semantykę dla rachunku probabilistycznego wyższego rzędu, który może cię zainteresować.

W ciągu ostatnich kilku lat prowadzona była bardzo aktywna linia badań wokół tzw. Ilościowej semantyki denotacyjnej logiki liniowej, oparta na idei (pierwotnie z powodu Girarda [1]), że programy wyższego rzędu mogą być modelowane za pomocą szeregów mocy. W przypadku probabilistycznym ma to postać tzw. Probabilistycznych przestrzeni koherencyjnych (PCS), również wprowadzonych przez Girarda [2] i zbadanych dogłębnie przez Danosa i Ehrharda [3]. PCS daje modele zarówno typowych, jak i nietypowych rachunków probabilistycznych, które mają zupełnie inny charakter niż domeny mocy i inne modele związane z monadami. W szczególności PCS dają jedyny znany do tej pory w pełni abstrakcyjny model probabilistycznego PCF [4], który jest niezwykle trudny i pozornie niemożliwy do osiągnięcia w domenach władzy (por. DziełoJean Goubault-Larrecq ).

Oprócz Ehrharda, semantyka ilościowa jest obecnie aktywnie rozwijana przez Michele Pagani i współautorów, sugeruję zajrzeć na jego stronę internetową w celu uzyskania dodatkowych odniesień.

$\lambda$

[2] Jean-Yves Girard, Między logiką a kwantem: traktat . W logice liniowej w informatyce , CUP, 2004.

[3] Vincent Danos i Thomas Ehrhard, Probabilistyczne przestrzenie koherencji jako model obliczeń probabilistycznych wyższego rzędu . Informacje i obliczenia 209 (6): 966–991, 2011.

[4] Thomas Ehrhard, Michele Pagani i Christine Tasson, Probabilistyczne przestrzenie spójności są w pełni abstrakcyjne dla probabilistycznego PCF . W Proceedings of POPL , s. 309–320, 2014.

Poniższy komentarz jest poprawny, ale ważne jest, aby zrozumieć znaczenie „skończonych” lub „zwartych” elementów domeny. Są to oznaczenia obiektów obliczalnych w skończonym czasie, więc ich pojawienie się w modelu semantycznym nie jest dla wygody teoretycznej - reprezentują silny związek między modelem a rzeczywistym obliczeniem.

Cóż, cytat Mislove'a zawiera już pozytywną odpowiedź: kategoria dcpos jest zamknięta kartezyjska, a także zamknięta pod probabilistyczną domeną potęgi. Rzeczywiście można go użyć do nadania denotacyjnej semantyki obliczeniom probabilistycznym wyższego rzędu. Jednak dcpos nie spełniają „zwykłych założeń aproksymacyjnych”, że każdy element można w pewnym sensie aproksymować elementami „skończonymi”, jak ma to miejsce w przypadku algebraicznych i ciągłych cpos. Założenia te pomagają w pewnych argumentach denotacyjnych, ale nie są potrzebne, aby dać semantykę per se.