Исчисление взаимодействующих систем ( англ. Calculus of Communicating Systems , CCS , исчисление общающихся систем ) в информатике — исчисление процессов , разработанное Робином Милнером в 1980 году. Исчисление работает с моделью неразделяемых коммуникаций между ровно двумя участниками. Формальный язык включает примитивы для описания параллельной композиции, выбора между действиями и рамки ограничений. CCS полезен для оценки качественной корректности свойств таких как взаимная блокировка или « живая блокировка » .

Согласно Милнеру, «нет ничего канонического в выборе базовых комбинаторов, даже несмотря на то, что они были выбраны с большим вниманием к экономии. То, что характеризует наше исчисление, это не точный выбор комбинаторов, но выбор интерпретации и математической структуры » .

Выражения языка интерпретируются как . Между этими моделями используется как семантическая эквивалентность.

Синтаксис

Для данного множества имён действий, множество CCS-процессов определяется следующей грамматикой Бэкуса — Наура :

${\displaystyle P::=\emptyset \,\,\,|\,\,\,a.P_{1}\,\,\,|\,\,\,A\,\,\,|\,\,\,P_{1}+P_{2}\,\,\,|\,\,\,P_{1}|P_{2}\,\,\,|\,\,\,P_{1}[b/a]\,\,\,|\,\,\,P_{1}{\backslash }a}$

Части синтаксиса в данном выше порядке:

пустой процесс

пустой процесс ${\displaystyle \emptyset }$ — это валидный CCS-процесс

действие

процесс ${\displaystyle a.P_{1}}$ может совершать действие ${\displaystyle a}$ и продолжиться как процесс ${\displaystyle P_{1}}$

идентификатор процесса

пишем ${\displaystyle A{\overset {\underset {\mathrm {def} }{}}{=}}P_{1}}$ для использования идентификатора ${\displaystyle A}$ , чтобы ссылаться на процесс ${\displaystyle P_{1}}$

выбор

процесс ${\displaystyle P_{1}+P_{2}}$ может продолжаться либо как ${\displaystyle P_{1}}$ , либо как ${\displaystyle P_{2}}$

параллельная композиция

процессы ${\displaystyle P_{1}}$ и ${\displaystyle P_{2}}$ , существующие одновременно

переименование

${\displaystyle P_{1}[b/a]}$ процесс ${\displaystyle P_{1}}$ с действиями ${\displaystyle a}$ переименованными в ${\displaystyle b}$

ограничение

${\displaystyle P_{1}{\backslash }a}$ процесс ${\displaystyle P_{1}}$ без действия ${\displaystyle a}$

Схожие исчисления и модели

• ( англ. ), CSP — язык, разработанный Энтони Хоаром , который появился в то же время, что и CCS.
• Пи-исчисление , разработанное Милнером в конце 80-х, предоставляет подвижность коммуникационных звеньев, позволяя процессам сообщать имена самих коммуникационных каналов.
• Алгебра процессов , разработанная , вводит время действия и вероятностный выбор, позволяя вычислять метрики производительности.

Некоторые нотации, основанные на CCS:

• ( англ. );
• LOTOS .

Модели, которые используются в изучении CCS-систем:

• ( англ. );
• Модель акторов .

Ссылки

• Robin Milner: A Calculus of Communicating Systems , Springer Verlag, ISBN 0-387-10235-3 . 1980.
• Robin Milner, Communication and Concurrency , Prentice Hall, International Series in Computer Science, ISBN 0-13-115007-3 . 1989