Введение

В денотационной семантике и теории доменов, силовые домены – это домены недетерминированных и параллельных вычислений. Идея силовых доменов для функций заключается в том, что недетерминированную функцию можно описать как детерминированную функцию, принимающую на вход множество значений, содержащее все возможные результаты, которые недетерминированная функция может выдать для данного аргумента. Для параллельных систем идея состоит в том, чтобы выразить множество всех возможных траекторий вычислений. В общих чертах, силовой домен – это домен, элементы которого являются определенными подмножествами исходного домена. Однако, наивное применение этого подхода часто приводит к доменам, не обладающим необходимыми свойствами, что заставляет разрабатывать все более сложные определения силовых доменов. Существует три основных варианта: силовые домены Плоткина, верхний и нижний силовые домены. Один из способов понять эти концепции – рассматривать их как свободные модели теорий недетерминизма. На протяжении большей части этой статьи мы используем термины "домен" и "непрерывная функция" в достаточно широком смысле, подразумевая под ними, соответственно, некоторую упорядоченную структуру и функцию, сохраняющую пределы. Эта гибкость оправдана; например, в некоторых параллельных системах естественно требовать, чтобы каждое отправленное сообщение в конечном итоге было доставлено. Однако, предел цепочки приближений, в которой сообщение не было доставлено, будет представлять собой завершенное вычисление, в котором сообщение так и не было доставлено! Современным обзором этой темы является глава Абрамского и Юнга [1994]. Более ранние работы включают работы Плоткина [1983, глава 8] и Смита [1978].

Домены власти как свободные модели теорий недетерминизма

Теоретики доменов стали понимать домены власти абстрактно как свободные модели теорий недетерминизма. Подобно тому как конечное построение множества степеней является свободной полурешеткой, построения доменов власти следует понимать абстрактно как свободные модели теорий недетерминизма. Изменяя теории недетерминизма, получаются различные домены власти. Абстрактная характеристика доменов власти часто является наиболее удобным способом работы с ними, поскольку явные описания слишком сложны. (Исключением является домен власти Хоара, который имеет достаточно простое описание.)

Модели теорий движения

Модель теории мощности Плоткина является непрерывной полурешеткой: это полурешетка, носителем которой является домен и для которой операция является непрерывной. Следует отметить, что оператор не обязательно должен быть операцией взятия точной нижней грани или точной верхней грани для порядка в домене. Гомоморфизм непрерывных полурешеток — это непрерывная функция между их носителями, сохраняющая операцию полурешетки. Модели нижней теории мощности называются инфляционными полурешетками; существует дополнительное требование, чтобы оператор в некоторой степени вел себя как операция взятия точной верхней грани для порядка. Для верхней теории мощности модели называются дефляционными полурешетками; здесь оператор в некоторой степени ведет себя как операция взятия точной нижней грани.

Власть домены как свободные модели

Пусть D — домен. Поле мощностей Плоткина над D является свободной моделью теории мощностей Плоткина над D. Оно определяется как (если существует) модель P(D) теории мощностей Плоткина (то есть непрерывная полурешетка), снабженная непрерывным отображением D → P(D), таким что для любой другой непрерывной полурешетки L над D существует единственный непрерывный гомоморфизм полурешеток P(D) → L, делающий очевидную диаграмму коммутативной. Другие поля мощностей определяются абстрактно аналогичным образом.

Силовая область Клингера

Клингер [1981] построил домен мощностей для модели Actor, основываясь на базовом домене диаграмм событий Actor, который не является полным. См. модель Клингера.

Диаграммы с временем

Хьюитт [2006] построил силовую область для модели акторов (которая технически проще и легче для понимания, чем модель Клингера), основываясь на базовой области полных диаграмм событий акторов, определяемых по времени. Идея заключается в присвоении времени прибытия каждому сообщению, полученному актором. См. Модель диаграмм, определяемых по времени.

Связи с топологией и пространством Вьеториса

Домены могут рассматриваться как топологические пространства, и в этом контексте построения домена степеней могут быть соотнесены с построением пространства подмножеств, предложенным Леопольдом Виеторисом. См., например, [Smyth 1983].