Π-исчисление - Π-calculus

В теоретическая информатика, то $π$ -исчисление (или же пи-исчисление) это процесс исчисления. В $π$ -calculus позволяет передавать имена каналов по самим каналам, и таким образом он может описывать параллельные вычисления чья сетевая конфигурация может измениться во время вычислений.

В $π$ -calculus прост, в нем мало терминов, и поэтому это небольшой, но выразительный язык (видеть #Синтаксис ). Функциональные программы могут быть закодированы в $π$ -calculus, а кодировка подчеркивает диалоговую природу вычислений, устанавливая связи с семантика игры. Расширения $π$ -calculus, такой как исчисление spi и прикладное $π$ , успешно рассуждали о криптографические протоколы. Помимо первоначального использования при описании параллельных систем, $π$ -calculus также использовался, чтобы рассуждать о деловые процессы^[1] и молекулярная биология.^[2]

Неформальное определение

В $π$ -calculus принадлежит к семейству технологические расчеты, математические формализмы для описания и анализа свойств параллельных вычислений. Фактически, $π$ -calculus, как и λ-исчисление, настолько минимален, что не содержит примитивов, таких как числа, логические значения, структуры данных, переменные, функции или даже обычные операторы потока управления (например, если-то-еще, пока).

Конструкции процесса

Центральное место в $π$ -calculus - понятие имя. Простота исчисления заключается в двойной роли, которую играют имена как каналы связи и переменные.

В расчетах доступны следующие конструкции процессов.^[3] (точное определение дается в следующем разделе):

параллелизм, написано ${ displaystyle P mid Q}$ , куда ${ displaystyle P}$ и ${ displaystyle Q}$ это два процесса или потока, выполняемые одновременно.
коммуникация, куда
- префикс ввода ${ Displaystyle с влево (х вправо) .P}$ это процесс, ожидающий сообщения, которое было отправлено по каналу связи с именем ${ displaystyle c}$ прежде чем продолжить как ${ displaystyle P}$ , привязка полученного имени к имени $Икс$ . Обычно это моделирует либо процесс, ожидающий связи от сети, либо метку. c можно использовать только один раз goto c операция.
- префикс вывода ${ displaystyle { overline {c}} langle y rangle .P}$ описывает, что имя ${ displaystyle y}$ излучается на канале ${ displaystyle c}$ прежде чем продолжить как ${ displaystyle P}$ . Обычно это модели отправки сообщения в сети или goto c операция.
репликация, написано ${ Displaystyle! , P}$ , который можно рассматривать как процесс, который всегда может создать новую копию ${ displaystyle P}$ . Обычно это модель либо сетевой службы, либо метки. c ожидая любого количества goto c операции.
создание нового имени, написано ${ Displaystyle влево ( ню х вправо) P}$ , который можно рассматривать как процесс выделения новой константы $Икс$ в ${ displaystyle P}$ . Константы $π$ -исчисление определяются только своими именами и всегда являются каналами связи. Создание нового имени в процессе также называется ограничение.
нулевой процесс, написанный ${ displaystyle 0}$ , - это процесс, выполнение которого завершено и остановлено.

Хотя минимализм $π$ -calculus мешает нам писать программы в обычном понимании, это легко расширить исчисление. В частности, легко определить как управляющие структуры, такие как рекурсия, циклы и последовательная композиция, так и типы данных, такие как функции первого порядка, ценности истины, списки и целые числа. Более того, расширения $π$ -исчисление были предложены с учетом распределения или криптографии с открытым ключом. В применяемый $π$ -исчисление из-за Абади и Фурне [1] поставить эти различные расширения на формальную основу, расширив $π$ -исчисление с произвольными типами данных.

Небольшой пример

Ниже приведен крошечный пример процесса, который состоит из трех параллельных компонентов. Название канала $Икс$ известен только по первым двум компонентам.

{ Displaystyle { begin {align} ( nu x) & ; (; { overline {x}} langle z rangle. ; 0 & ; | ; x (y). ; { overline {y}} langle x rangle. ; x (y). ; 0 ;) & ; | ; z (v). ; { overline {v}} langle v rangle .0 end {align}}}

Первые два компонента могут обмениваться данными по каналу $Икс$ , и имя $у$ становится связанным с $z$ . Поэтому следующим шагом в этом процессе будет

{ Displaystyle { begin {align} ( nu x) & ; (; 0 & ; | ; { overline {z}} langle x rangle. ; x (y). ; 0 ;) & ; | ; z (v). ; { Overline {v}} langle v rangle. ; 0 end {align}}}

Обратите внимание, что оставшиеся $у$ не затрагивается, потому что он определен во внутренней области. Второй и третий параллельные компоненты теперь могут обмениваться данными по имени канала $z$ , и имя $v$ становится связанным с $Икс$ . Следующий шаг в процессе сейчас

{ Displaystyle { begin {align} ( nu x) & ; (; 0 & ; | ; x (y). ; 0 & ; | ; { overline {x }} langle x rangle. ; 0 ;) end {выравнивается}}}

Обратите внимание: поскольку местное имя $Икс$ был выведен, объем $Икс$ распространяется также на третий компонент. Наконец, канал $Икс$ можно использовать для отправки имени $Икс$ . После этого все одновременно выполняющиеся процессы остановились.

{ Displaystyle { begin {выровнено} ( ню х) & ; (; 0 & ; | ; 0 & ; | ; 0 ;) конец {выровнено}}}

Формальное определение

Синтаксис

Пусть Χ - множество объектов, называемых имена. В абстрактный синтаксис для $π$ -calculus построен из следующих Грамматика BNF (куда Икс и у любые имена из Χ):^[4]

{ displaystyle { begin {align} P, Q :: = & ; x (y) .P , , , , , & { text {Получение по каналу}} x { text {, привяжите результат к}} y { text {, затем запустите}} P & ; | ; { overline {x}} langle y rangle .P , , , , , & { text {Отправьте значение}} y { text {over channel}} x { text {, затем запустите}} P & ; | ; P | Q , , , , , , , , , & { text {Выполнить}} P { text {and}} Q { text {одновременно}} & ; | ; ( nu x) P , , , & { text {Создать новый канал}} x { text {и запустить}} P & ; | ;! P , , , & { text {Неоднократно создавать копии}} P & ; | ; 0 & { text {Завершить процесс}} end {align}}}

В конкретном синтаксисе ниже префиксы связываются сильнее, чем параллельная композиция (|), а скобки используются для устранения неоднозначности.

Имена связаны конструкциями ограничения и входного префикса. Формально набор свободных имен процесса в $π$ –Calculus определяются индуктивно по таблице ниже. Набор связанных имен процесса определяется как имена процесса, не входящие в набор свободных имен.

Построить	Бесплатные имена
${ displaystyle 0}$	Никто
${ displaystyle { overline {a}} langle x rangle .P}$	а; Икс; все бесплатные имена п
${ Displaystyle а (х) .P}$	а; бесплатные имена п кроме Икс
${ displaystyle P \| Q}$	Все бесплатные имена п и Q
${ Displaystyle ( ню х) .P}$	Бесплатные имена п кроме Икс
${ displaystyle! P}$	Все бесплатные имена п

Структурное соответствие

Центральным как для семантики редукции, так и для семантики помеченных переходов является понятие структурное соответствие. Два процесса структурно конгруэнтны, если они идентичны по структуре. В частности, параллельная композиция коммутативна и ассоциативна.

Точнее, структурная конгруэнтность определяется как отношение наименьшей эквивалентности, сохраняемое конструкциями процесса и удовлетворяющее:

Альфа-преобразование:

${ Displaystyle P Equiv Q}$ если ${ displaystyle Q}$ можно получить из ${ displaystyle P}$ переименовав одно или несколько связанных имен в ${ displaystyle P}$ .

Аксиомы параллельной композиции:

${ Displaystyle P | Q Equiv Q | P}$
${ Displaystyle (P | Q) | R эквив P | (Q | R)}$
${ Displaystyle P | 0 Equiv P}$

Аксиомы ограничения:

${ Displaystyle ( ню х) ( ню у) п экв ( ню у) ( ню х) п}$
${ Displaystyle ( ню х) 0 эквив 0}$

Аксиома для репликации:

${ Displaystyle! P Equiv P |! P}$

Аксиома, связывающая ограничение и параллель:

${ Displaystyle ( ню х) (п | Q) экв ( ню х) п | Q}$ если $Икс$ это не свободное имя ${ displaystyle Q}$ .

Эта последняя аксиома известна как аксиома «расширения области видимости». Эта аксиома является центральной, поскольку она описывает, как связанное имя $Икс$ может быть выдавлен выходным действием, вызывая область действия $Икс$ будет продлен. В случаях, когда $Икс$ это свободное имя ${ displaystyle Q}$ , альфа-преобразование может быть использовано для продолжения расширения.

Семантика редукции

Мы пишем ${ displaystyle P rightarrow P '}$ если ${ displaystyle P}$ может выполнить шаг вычисления, после которого он теперь ${ displaystyle P '}$ .Этот редукционное отношение ${ displaystyle rightarrow}$ определяется как наименьшее отношение, замкнутое по набору правил редукции.

Основное правило редукции, которое учитывает способность процессов взаимодействовать через каналы, следующее:

${ displaystyle { overline {x}} langle z rangle .P | x (y) .Q rightarrow P | Q [z / y]}$

куда

{ Displaystyle Q [г / у]}

обозначает процесс

{ displaystyle Q}

в котором бесплатное имя

{ displaystyle z}

был заменен для свободного появления

{ displaystyle y}

. Если свободное появление

{ displaystyle y}

происходит в месте, где

{ displaystyle z}

не будет бесплатным, может потребоваться альфа-преобразование.

Есть три дополнительных правила:

Если ${ displaystyle P rightarrow Q}$ тогда также ${ Displaystyle P | R rightarrow Q | R}$ .

Это правило гласит, что параллельная композиция не препятствует вычислениям.

Если ${ displaystyle P rightarrow Q}$ , то также ${ Displaystyle ( ню х) п вправо ( ню х) Q}$ .

Это правило гарантирует, что вычисления могут продолжаться без ограничений.

Если ${ Displaystyle P Equiv P '}$ и ${ displaystyle P ' rightarrow Q'}$ и ${ Displaystyle Q ' Equiv Q}$ , то также ${ displaystyle P rightarrow Q}$ .

Последнее правило гласит, что структурно конгруэнтные процессы имеют одинаковые редукции.

Повторный пример

Рассмотрим еще раз процесс

{ Displaystyle ( nu x) ({ overline {x}} langle z rangle .0 | x (y). { overline {y}} langle x rangle .x (y) .0) | z (v). { overline {v}} langle v rangle .0}

Применяя определение семантики редукции, получаем редукцию

{ Displaystyle ( nu x) ({ overline {x}} langle z rangle .0 | x (y). { overline {y}} langle x rangle .x (y) .0) | z (v). { overline {v}} langle v rangle .0 rightarrow ( nu x) (0 | { overline {z}} langle x rangle .x (y) .0) | z (v). { overline {v}} langle v rangle .0}

Обратите внимание, как, применяя аксиому подстановки редукции, свободные вхождения ${ displaystyle y}$ теперь помечены как ${ displaystyle z}$ .

Далее получаем сокращение

{ displaystyle ( nu x) (0 | { overline {z}} langle x rangle .x (y) .0) | z (v). { overline {v}} langle v rangle. 0 rightarrow ( nu x) (0 | x (y) .0 | { overline {x}} langle x rangle .0)}

Обратите внимание: поскольку местное имя $Икс$ был выведен, объем $Икс$ распространяется также на третий компонент. Это было зафиксировано с помощью аксиомы расширения области действия.

Далее, используя аксиому подстановки редукции, получаем

{ Displaystyle ( ню х) (0 | 0 | 0)}

Наконец, используя аксиомы параллельной композиции и ограничения, получаем

{ displaystyle 0}

Помеченная семантика

В качестве альтернативы можно дать пи-исчислению маркированную семантику перехода (как это было сделано с Расчет коммуникационных систем ).
В этой семантике переход из состояния ${ displaystyle P}$ в какое-то другое государство ${ displaystyle P '}$ после действия ${ displaystyle alpha}$ обозначается как:

${ Displaystyle P , { xrightarrow { overset {} { alpha}}} P '}$

Где говорится ${ displaystyle P}$ и ${ displaystyle P '}$ представляют процессы и ${ displaystyle alpha}$ является либо действие ввода ${ Displaystyle а (х)}$ , выходное действие ${ displaystyle { overline {a}} langle x rangle}$ , или тихое действие $τ$ .^[5]

Стандартный результат в отношении помеченной семантики состоит в том, что она согласуется с семантикой редукции в том смысле, что ${ displaystyle P rightarrow P '}$ если и только если ${ Displaystyle P , { xrightarrow { overset {} { alpha}}} P '}$ для какого-то действия ${ displaystyle alpha}$ ^{[нужна цитата ]}.

Расширения и варианты

Приведенный выше синтаксис минимален. Однако синтаксис можно изменять по-разному.

А недетерминированный оператор выбора ${ displaystyle P + Q}$ можно добавить в синтаксис.

Тест на имя равенство ${ displaystyle [x = y] P}$ можно добавить в синтаксис. Этот оператор соответствия может действовать как ${ displaystyle P}$ если и только если $Икс$ и ${ displaystyle y}$ одно и то же имя. Точно так же можно добавить оператор несовпадения за название неравенство. Практические программы, которые могут передавать имена (URL-адреса или указатели), часто используют такую функциональность: для прямого моделирования такой функциональности внутри исчисления часто бывает полезно это и связанные с ним расширения.

В асинхронный $π$ -исчисление^[6]^[7]разрешает только выходы без суффикса, то есть выходные атомы в форме ${ displaystyle { overline {x}} langle y rangle}$ , что дает меньшее исчисление. Однако любой процесс в исходном исчислении может быть представлен меньшим асинхронным $π$ -calculus с использованием дополнительного канала для имитации явного подтверждения от принимающего процесса. Поскольку выходные данные без продолжения могут моделировать сообщение в пути, этот фрагмент показывает, что исходный $π$ -calculus, который интуитивно основан на синхронной коммуникации, имеет выразительную асинхронную коммуникационную модель внутри своего синтаксиса. Однако недетерминированный оператор выбора, определенный выше, не может быть выражен таким образом как неохраняемый выбор превратится в осторожный; этот факт был использован для демонстрации того, что асинхронное исчисление строго менее выразительно, чем синхронное (с оператором выбора).^[8]

В полиадический $π$ -исчисление позволяет передавать более одного имени в одном действии: ${ displaystyle { overline {x}} langle z_ {1}, ..., z_ {n} rangle .P}$ (полиадический вывод) и ${ Displaystyle х (z_ {1}, ..., z_ {n}). P}$ (полиадический ввод). Это полиадическое расширение, которое полезно, особенно при изучении типов для процессов передачи имен, может быть закодировано в монадическом исчислении путем передачи имени частного канала, через который затем последовательно передаются несколько аргументов. Кодировка определяется рекурсивно с помощью предложений

${ displaystyle { overline {x}} langle y_ {1}, cdots, y_ {n} rangle .P}$ кодируется как ${ displaystyle ( nu w) { overline {x}} langle w rangle. { overline {w}} langle y_ {1} rangle. cdots. { overline {w}} langle y_ {n} rangle. [P]}$

${ Displaystyle х (y_ {1}, cdots, y_ {n}). P}$ кодируется как ${ Displaystyle x (w) .w (y_ {1}). cdots .w (y_ {n}). [P]}$

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

В приведенном выше описании ${ displaystyle [P]}$ обозначает кодировку всех префиксов в продолжении ${ displaystyle P}$ таким же образом.

Полная сила репликации ${ displaystyle! P}$ не нужен. Часто только рассматривают реплицированный ввод ${ Displaystyle! х (у) .P}$ , аксиома структурной конгруэнтности которого ${ Displaystyle! х (у) .P эквив х (у) .P |! х (у) .P}$ .

Реплицированный процесс ввода, такой как ${ Displaystyle! х (у) .P}$ можно понимать как серверы, ожидающие на канале $Икс$ для вызова клиентами. Вызов сервера порождает новую копию процесса ${ Displaystyle P [а / у]}$ , где a - это имя, переданное клиентом серверу во время его вызова.

А более высокого порядка $π$ -исчисление может быть определено, где не только имена, но и процессы отправляются по каналам. Правило сокращения ключа для случая более высокого порядка:

${ displaystyle { overline {x}} langle R rangle .P | x (Y) .Q rightarrow P | Q [R / Y]}$

Здесь, ${ displaystyle Y}$ обозначает переменная процесса который может быть инстанцирован термином процесса. Сангиоргией установлено, что способность передавать процессы не увеличивает выразительность $π$ -calculus: прохождение процесса п можно смоделировать, просто передав имя, указывающее на п вместо.

Характеристики

Полнота по Тьюрингу

В $π$ -calculus - это универсальная модель вычислений. Впервые это заметил Milner в своей статье «Функции как процессы»,^[9] в котором он представляет две кодировки лямбда-исчисление в $π$ -исчисление. Одна кодировка имитирует стремление (по значению) стратегия оценки, другая кодировка моделирует стратегию обычного порядка (вызов по имени). В обоих случаях ключевым моментом является моделирование привязок среды - например, " $Икс$ обязательно к сроку ${ textstyle M}$ "- как реплицирующие агенты, которые отвечают на запросы своих привязок, отправляя обратно соединение с термином ${ displaystyle M}$ .

Особенности $π$ -calculus, которые делают возможным такое кодирование, - это передача имен и репликация (или, что то же самое, рекурсивно определенные агенты). В отсутствие репликации / рекурсии $π$ -calculus перестает быть Тьюринг -мощный. Это видно по тому факту, что бисимуляция эквивалентность становится разрешимой для безрекурсивного исчисления и даже для конечного управления $π$ -вычисление, где количество параллельных компонентов в любом процессе ограничено константой.^[10]

Бисимуляции в $π$ -исчисление

Что касается технологических расчетов, $π$ -calculus позволяет определить эквивалентность бимимуляции. в $π$ -calculus, определение эквивалентности бисимуляции (также известной как двойное сходство) может быть основано либо на семантике редукции, либо на семантике помеченного перехода.

Есть (как минимум) три разных способа определения маркированная бисимуляционная эквивалентность в $π$ -calculus: раннее, позднее и открытое двойное сходство. Это связано с тем, что $π$ -calculus - это исчисление процесса передачи значений.

В оставшейся части этого раздела мы полагаем ${ displaystyle p}$ и ${ displaystyle q}$ обозначают процессы и ${ displaystyle R}$ обозначают бинарные отношения над процессами.

Раннее и позднее двойное сходство

И раннее, и позднее двойное сходство были сформулированы Милнером, Парроу и Уокером в их оригинальной статье о $π$ -исчисление.^[11]

Бинарное отношение ${ displaystyle R}$ над процессами ранняя бисимуляция если для каждой пары процессов ${ displaystyle (p, q) in R}$ ,

в любое время ${ displaystyle p , { xrightarrow {a (x)}} , p '}$ затем для каждого имени ${ displaystyle y}$ есть некоторые ${ displaystyle q '}$ такой, что ${ Displaystyle д , { xrightarrow {а (х)}} , д '}$ и ${ Displaystyle (п '[у / х], д' [у / х]) в R}$ ;
для любого действия без ввода ${ displaystyle alpha}$ , если ${ displaystyle {p { xrightarrow { overset {} { alpha}}} p '}}$ тогда есть некоторые ${ displaystyle q '}$ такой, что ${ displaystyle q { xrightarrow { overset {} { alpha}}} q '}$ и ${ displaystyle (p ', q') in R}$ ;
и симметричные требования с ${ displaystyle p}$ и ${ displaystyle q}$ поменялись местами.

Процессы ${ displaystyle p}$ и ${ displaystyle q}$ считаются ранними бисимилярами, написаны ${ displaystyle p sim _ {e} q}$ если пара ${ displaystyle (p, q) in R}$ для ранней бисимуляции ${ displaystyle R}$ .

При позднем двойном сходстве совпадение перехода не должно зависеть от передаваемого имени. ${ displaystyle R}$ над процессами поздняя бисимуляция если для каждой пары процессов ${ displaystyle (p, q) in R}$ ,

в любое время ${ Displaystyle р { xrightarrow {а (х)}} р '}$ тогда для некоторых ${ displaystyle q '}$ он считает, что ${ Displaystyle д { xrightarrow {а (х)}} д '}$ и ${ Displaystyle (п '[у / х], д' [у / х]) в R}$ для каждого имени y;
для любого действия без ввода ${ displaystyle alpha}$ , если ${ displaystyle p { xrightarrow { overset {} { alpha}}} p '}$ означает, что существуют некоторые ${ displaystyle q '}$ такой, что ${ displaystyle q { xrightarrow { overset {} { alpha}}} q '}$ и ${ displaystyle (p ', q') in R}$ ;
и симметричные требования с ${ displaystyle p}$ и ${ displaystyle q}$ поменялись местами.

Процессы ${ displaystyle p}$ и ${ displaystyle q}$ говорят, что опаздывают, написаны ${ displaystyle p sim _ {l} q}$ если пара ${ displaystyle (p, q) in R}$ для некоторой поздней бисимуляции ${ displaystyle R}$ .

Обе ${ displaystyle sim _ {e}}$ и ${ displaystyle sim _ {l}}$ страдают от проблемы, что они не отношения конгруэнтности в том смысле, что они сохраняются не всеми конструкциями процесса. Точнее, существуют процессы ${ displaystyle p}$ и ${ displaystyle q}$ такой, что ${ displaystyle p sim _ {e} q}$ но ${ Displaystyle а (х) .p not sim _ {е} а (х) .q}$ . Эту проблему можно решить, рассматривая максимальные соотношения конгруэнтности, включенные в ${ displaystyle sim _ {e}}$ и ${ displaystyle sim _ {l}}$ , известный как ранняя конгруэнтность и поздняя конгруэнтность, соответственно.

Открытое двойное сходство

К счастью, возможно третье определение, позволяющее избежать этой проблемы, а именно определение открытое двойное сходство, благодаря Санджорджи.^[12]

Бинарное отношение ${ displaystyle R}$ над процессами открытая бисимуляция если для каждой пары элементов ${ displaystyle (p, q) in R}$ и при каждой подмене имени ${ displaystyle sigma}$ и каждое действие ${ displaystyle alpha}$ , в любое время ${ displaystyle p sigma { xrightarrow { overset {} { alpha}}} p '}$ тогда есть некоторые ${ displaystyle q '}$ такой, что ${ Displaystyle q sigma { xrightarrow { overset {} { alpha}}} q '}$ и ${ displaystyle (p ', q') in R}$ .

Процессы ${ displaystyle p}$ и ${ displaystyle q}$ называются открытыми бисквитными, написанными ${ displaystyle p sim _ {o} q}$ если пара ${ displaystyle (p, q) in R}$ для некоторой открытой бисимуляции ${ displaystyle R}$ .

Различают раннее, позднее и открытое двойное сходство.

Различают раннее, позднее и открытое двойное сходство. Условия содержания в порядке, поэтому ${ displaystyle sim _ {o} subsetneq sim _ {l} subsetneq sim _ {e}}$ .

Известно, что в некоторых субвычислениях, таких как асинхронное пи-исчисление, поздняя, ранняя и открытая двойственность совпадают. Однако в этом контексте более подходящим понятием является понятие асинхронное двойное сходство.В литературе термин открытая бисимуляция обычно относится к более сложным понятиям, в которых процессы и отношения индексируются отношениями различения; подробности можно найти в цитированной выше статье Санджорджи.

Колючая эквивалентность

В качестве альтернативы можно определить эквивалентность бисимуляции непосредственно из семантики редукции. Мы пишем ${ displaystyle p Downarrow a}$ если процесс ${ displaystyle p}$ сразу разрешает ввод или вывод по имени ${ displaystyle a}$ .

Бинарное отношение ${ displaystyle R}$ над процессами колючая бисимуляция если это симметричное отношение, удовлетворяющее тому, что для каждой пары элементов ${ displaystyle (p, q) in R}$ у нас есть это

(1)

{ displaystyle p Downarrow a}

если и только если

{ displaystyle q Downarrow a}

для каждого имени

{ displaystyle a}

и

(2) для каждого сокращения

{ displaystyle p rightarrow p '}

существует редукция

{ displaystyle q rightarrow q '}

такой, что ${ displaystyle (p ', q') in R}$ .

Мы говорим что ${ displaystyle p}$ и ${ displaystyle q}$ находятся колючий бисимиляр если существует колючая бисимуляция ${ displaystyle R}$ куда ${ displaystyle (p, q) in R}$ .

Определение контекста как $π$ член с дыркой [] мы говорим, что два процесса P и Q колючий конгруэнтный, написано ${ Displaystyle P sim _ {b} Q , !}$ , если для каждого контекста ${ displaystyle C []}$ у нас есть это ${ displaystyle C [P]}$ и ${ displaystyle C [Q]}$ бизимиляры с колючками. Оказывается, колючая конгруэнтность совпадает с конгруэнцией, индуцированной ранним двусобием.

Приложения

В $π$ -calculus использовался для описания множества различных типов параллельных систем. Фактически, некоторые из самых последних приложений лежат за пределами области традиционной информатики.

В 1997 г. Мартин Абади и Эндрю Гордон предложил продлить $π$ -calculus, Spi-исчисление, как формальная нотация для описания и рассуждений о криптографических протоколах. Spi-исчисление расширяет $π$ -calculus с примитивами для шифрования и дешифрования. В 2001, Мартин Абади и Седрик Фурнет обобщил обработку криптографических протоколов для создания прикладных $π$ исчисление. В настоящее время существует большой объем работ, посвященных вариантам применяемого $π$ исчисление, включая ряд экспериментальных средств проверки. Одним из примеров является инструмент ProVerif [2] благодаря Бруно Бланше, на основе перевода прикладной $π$ -вычисление в структуру логического программирования Бланше. Другой пример - Cryptyc. [3], благодаря Эндрю Гордону и Алану Джеффри, которые используют метод утверждений соответствия Ву и Лэма в качестве основы для систем типов, которые могут проверять свойства аутентификации криптографических протоколов.

Примерно в 2002 году Говард Смит и Питер Фингар заинтересовались тем, что $π$ -calculus станет инструментом описания для моделирования бизнес-процессов. К июлю 2006 года в сообществе обсуждают, насколько это было бы полезно. Совсем недавно $π$ -calculus сформировал теоретическую основу Язык моделирования бизнес-процессов (BPML) и Microsoft XLANG.^[13]

В $π$ -calculus также привлек интерес к молекулярной биологии. В 1999 году, Авив Регев и Эхуд Шапиро показали, что можно описать клеточный сигнальный путь (так называемый RTK /MAPK каскад) и, в частности, молекулярный «лего», который реализует эти задачи коммуникации в расширении $π$ -исчисление.^[2] После этой основополагающей статьи другие авторы описали всю метаболическую сеть минимальной клетки.^[14] В 2009 году Энтони Нэш и Сара Калвала предложил $π$ -счетчик для моделирования передачи сигнала, который направляет Dictyostelium discoideum агрегация.^[15]

История

В $π$ -calculus был первоначально разработан Робин Милнер, Иоахим Парроу и Дэвид Уокер в 1992 году, основанные на идеях Уффе Энгберга и Могенса Нильсена.^[16] Его можно рассматривать как продолжение работы Милнера по исчислению процессов CCS (Расчет коммуникационных систем ). В своей лекции Тьюринга Милнер описывает развитие $π$ -calculus как попытка уловить единообразие ценностей и процессов в акторах.^[17]

Реализации

Следующие языки программирования являются реализациями любого из $π$ -calculus или его варианты:

Язык моделирования бизнес-процессов (BPML)
Оккам-π
Pict
JoCaml (на основе Соединение-исчисление )
RhoLang

Примечания

^ Спецификация OMG (2011 г.). «Модель бизнес-процесса и нотация (BPMN) Версия 2.0», Группа управления объектами. стр.21
^ ^а ^б Регев, Авив; Уильям Сильверман; Эхуд Ю. Шапиро (2001). "Представление и моделирование биохимических процессов с использованием алгебры процессов пи-исчисления". Тихоокеанский симпозиум по биокомпьютингу: 459–470.
^ Wing, Жаннетт М. (27 декабря 2002 г.). «FAQ по π-исчислению» (PDF).
^ Расчет мобильных процессов, часть 1 стр. 10, Р. Милнер, Дж. Парроу и Д. Уокер, опубликованные в Information and Computation 100 (1) pp. 1-40, сентябрь 1992 г.
^ Робин Милнер, Коммуникационные и мобильные системы: вычисление числа Пи, Cambridge University Press, ISBN 0521643201. 1999
^ Будоль, Г. (1992). Асинхронность и $π$ -исчисление. Технический отчет 1702, INRIA, София-Антиполис.
^ Honda, K .; Токоро, М. (1991). Объектное исчисление для асинхронной связи. ECOOP 91. Springer Verlag.
^ Паламидесси, Катуша (1997). «Сравнение выразительной силы синхронного и асинхронного пи-исчисления». Материалы 24-го симпозиума ACM по принципам языков программирования: 256–265. arXiv:cs / 9809008. Bibcode:1998cs ........ 9008P.
^ Милнер, Робин (1992). «Функции как процессы» (PDF). Математические структуры в информатике. 2 (2): 119–141. Дои:10.1017 / s0960129500001407.
^ Плотина, Мэдс (1997). «О разрешимости эквивалентностей процессов для пи-исчисления». Теоретическая информатика. 183 (2): 215–228. Дои:10.1016 / S0304-3975 (96) 00325-8.
^ Milner, R .; Дж. Парроу; Д. Уокер (1992). «Исчисление мобильных процессов» (PDF). Информация и вычисления. 100 (1): 1–40. Дои:10.1016/0890-5401(92)90008-4.
^ Санджорджи, Д. (1996). «Теория бисимуляции для π-исчисления». Acta Informatica. 33: 69–97. Дои:10.1007 / s002360050036.
^ «BPML | BPEL4WS: путь конвергенции к стандартному стеку BPM». Документ с изложением позиции BPMI.org. 15 августа 2002 г.
^ Кьяруги, Давиде; Пьерпаоло Дегано; Роберто Марангони (2007). «Вычислительный подход к функциональному скринингу геномов». PLOS вычислительная биология. 3 (9): 1801–1806. Дои:10.1371 / journal.pcbi.0030174. ЧВК 1994977. PMID 17907794.
^ Nash, A .; Калвала, С. (2009). «Основное предложение для клеточной локальности Dictyostelium, смоделированное в π-исчислении» (PDF). CoSMoS 2009.
^ Engberg, U .; Нильсен, М. (1986). «Расчет систем связи с передачей меток». Серия отчетов DAIMI. 15 (208). Дои:10.7146 / dpb.v15i208.7559.
^ Робин Милнер (1993). «Элементы взаимодействия: лекция о премии Тьюринга». Commun. ACM. 36 (1): 78–89. Дои:10.1145/151233.151240.

внешняя ссылка

PiCalculus в C2 вики
FAQ по π-исчислению к Жаннетт М. Винг

[omg-1] Спецификация OMG (2011 г.). «Модель бизнес-процесса и нотация (BPMN) Версия 2.0», Группа управления объектами. стр.21

[reeve-2] а ^б Регев, Авив; Уильям Сильверман; Эхуд Ю. Шапиро (2001). "Представление и моделирование биохимических процессов с использованием алгебры процессов пи-исчисления". Тихоокеанский симпозиум по биокомпьютингу: 459–470.

[3] Wing, Жаннетт М. (27 декабря 2002 г.). «FAQ по π-исчислению» (PDF).

[4] Расчет мобильных процессов, часть 1 стр. 10, Р. Милнер, Дж. Парроу и Д. Уокер, опубликованные в Information and Computation 100 (1) pp. 1-40, сентябрь 1992 г.

[5] Робин Милнер, Коммуникационные и мобильные системы: вычисление числа Пи, Cambridge University Press, ISBN 0521643201. 1999

[6] Будоль, Г. (1992). Асинхронность и $π$ -исчисление. Технический отчет 1702, INRIA, София-Антиполис.

[7] Honda, K .; Токоро, М. (1991). Объектное исчисление для асинхронной связи. ECOOP 91. Springer Verlag.

[8] Паламидесси, Катуша (1997). «Сравнение выразительной силы синхронного и асинхронного пи-исчисления». Материалы 24-го симпозиума ACM по принципам языков программирования: 256–265. arXiv:cs / 9809008. Bibcode:1998cs ........ 9008P.

[9] Милнер, Робин (1992). «Функции как процессы» (PDF). Математические структуры в информатике. 2 (2): 119–141. Дои:10.1017 / s0960129500001407.

[10] Плотина, Мэдс (1997). «О разрешимости эквивалентностей процессов для пи-исчисления». Теоретическая информатика. 183 (2): 215–228. Дои:10.1016 / S0304-3975 (96) 00325-8.

[11] Milner, R .; Дж. Парроу; Д. Уокер (1992). «Исчисление мобильных процессов» (PDF). Информация и вычисления. 100 (1): 1–40. Дои:10.1016/0890-5401(92)90008-4.

[12] Санджорджи, Д. (1996). «Теория бисимуляции для π-исчисления». Acta Informatica. 33: 69–97. Дои:10.1007 / s002360050036.

[13] «BPML | BPEL4WS: путь конвергенции к стандартному стеку BPM». Документ с изложением позиции BPMI.org. 15 августа 2002 г.

[14] Кьяруги, Давиде; Пьерпаоло Дегано; Роберто Марангони (2007). «Вычислительный подход к функциональному скринингу геномов». PLOS вычислительная биология. 3 (9): 1801–1806. Дои:10.1371 / journal.pcbi.0030174. ЧВК 1994977. PMID 17907794.

[15] Nash, A .; Калвала, С. (2009). «Основное предложение для клеточной локальности Dictyostelium, смоделированное в π-исчислении» (PDF). CoSMoS 2009.

[16] Engberg, U .; Нильсен, М. (1986). «Расчет систем связи с передачей меток». Серия отчетов DAIMI. 15 (208). Дои:10.7146 / dpb.v15i208.7559.

[17] Робин Милнер (1993). «Элементы взаимодействия: лекция о премии Тьюринга». Commun. ACM. 36 (1): 78–89. Дои:10.1145/151233.151240.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Параллельные вычисления
Общий	Параллелизм Контроль параллелизма
Расчет процесса	CSP CCS ACP LOTOS π-исчисление Окружающий расчет API-исчисление PEPA Соединение-исчисление
Классические проблемы	Проблема ABA Проблема курильщиков сигарет Тупик Проблема обедающих философов Проблема производителя и потребителя Состояние гонки Проблема читателей – писателей Проблема сна парикмахера Проблема чтения из непостоянной записи
Категория: Параллельные вычисления

Π-исчисление - Π-calculus

Содержание

Неформальное определение

Конструкции процесса

Небольшой пример

Формальное определение

Синтаксис

Структурное соответствие

Семантика редукции

Повторный пример

Помеченная семантика

Расширения и варианты

Характеристики

Полнота по Тьюрингу

Бисимуляции в $π$ -исчисление

Раннее и позднее двойное сходство

Открытое двойное сходство

Различают раннее, позднее и открытое двойное сходство.

Колючая эквивалентность

Приложения

История

Реализации

Примечания

Рекомендации

внешняя ссылка

Π-исчисление - Π-calculus

Неформальное определение

Конструкции процесса

Небольшой пример

Формальное определение

Синтаксис

Структурное соответствие

Семантика редукции

Повторный пример

Помеченная семантика

Расширения и варианты

Характеристики

Полнота по Тьюрингу

Бисимуляции в π-исчисление

Раннее и позднее двойное сходство

Открытое двойное сходство

Различают раннее, позднее и открытое двойное сходство.

Колючая эквивалентность

Приложения

История

Реализации

Примечания

Рекомендации

внешняя ссылка

Бисимуляции в $π$ -исчисление