WikiDer > Силовые домены

Power domains

В денотационная семантика и теория предметной области, силовые домены являются доменами недетерминированный и одновременный вычисления.

Идея степенных областей для функций состоит в том, что недетерминированная функция может быть описана как детерминированная многозначная функция, где набор содержит все значения, которые недетерминированная функция может принимать для данного аргумента. Для параллельных систем идея состоит в том, чтобы выразить набор всех возможных вычислений.

Грубо говоря, степенная область - это область, элементами которой являются определенные подмножества области. Однако наивный подход к такому подходу часто приводит к появлению доменов, которые не совсем обладают желаемыми свойствами, что приводит ко все более усложненным понятиям области власти. Есть три распространенных варианта: область Плоткина, верхняя и нижняя области мощности. Один из способов понять эти концепции - это свободные модели теорий недетерминизма.

В большей части этой статьи мы используем термины «область» и «непрерывная функция» довольно свободно, имея в виду, соответственно, некую упорядоченную структуру и некоторую функцию, сохраняющую предел. Эта гибкость подлинна; например, в некоторых параллельных системах естественно наложить условие, согласно которому каждое отправленное сообщение должно в конечном итоге быть доставлено. Однако предел цепочки приближений, в которой сообщение не было доставлено, будет завершенным вычислением, в котором сообщение никогда не было доставлено!

Современное упоминание об этом предмете - глава Abramsky and Jung [1994]. Более старые ссылки включают в себя Плоткина [1983, глава 8] и Смита [1978].

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

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

Абстрактная характеристика мощных доменов часто является самым простым способом работы с ними, потому что явные описания настолько сложны. (Единственным исключением является область власти Хоара, имеющая довольно простое описание.)

Теории недетерминизма

Напомним три теории недетерминизма. Это вариации теории полурешетки. Теории не являются алгебраическими теориями в общепринятом смысле, потому что некоторые из них связаны с порядком основной области.

Все теории имеют один вид Икс, и одна бинарная операция ∪. По идее, операция $\cup: Икс \times Икс \to Икс$ берет две комбинации и возвращает их недетерминированный выбор.

В Плоткин powertheory (после Гордон Плоткин) имеет один вид, Икс, и следующие аксиомы:

Идемпотентность: Икс∪Икс=Икс
Коммутативность: Икс∪у=у∪Икс
Ассоциативность: (Икс∪у)∪z=Икс∪(у∪z)

В ниже (или же Hoare, после Тони Хоар) теория мощности состоит из теории мощности Плоткина, дополненной неравенством

Икс≤Икс∪у.

В верхний (или же Смит, после М. Б. Смита) теория мощности состоит из теории мощности Плоткина, дополненной неравенством

Икс∪у≤Икс.

Модели теорий власти

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

Модели теории низких степеней называются инфляционными полурешетками; есть дополнительное требование, чтобы оператор вёл себя немного как соединение для заказа. Для теории верхних степеней модели называются дефляционными полурешетками; здесь оператор ведет себя как на соревнованиях.

Энергетические домены как бесплатные модели

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

Аналогичным образом абстрактно определяются другие области мощности.

Явные описания областей власти

Позволять D быть доменом. Область более низкой мощности может быть определена как

п[D] = {закрытие [А] | Ø∈А⊆D} куда

закрытие[А] = {d∈D | ∃Икс⊆D, Икс направленный, d =

{ displaystyle vee}

Икс, и ∀Икс∈Икс ∃а∈А Икс≤а}.

Другими словами, п[D] - это набор замкнутых вниз подмножеств D которые также замкнуты относительно существующих наименьших верхних границ направленных множеств в D. Обратите внимание, что при заказе на п[D] задается отношением подмножества, точные верхние оценки, вообще говоря, не совпадают с объединениями.

Важно проверить, какие свойства доменов сохраняются при построении степенных доменов. Например, область степеней Хоара ω-полной области снова является ω-полной.

Силовые домены для параллелизма и участников

Власть Клингера

Clinger [1981] построил область мощности для Актерская модель опираясь на базовый домен Диаграммы актерских событий, что является неполным. Видеть Модель Клингера.

Временные диаграммы в области мощности

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

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

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

Navigation