Interested Article - Исчисление взаимодействующих систем

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

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

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

Синтаксис

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

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

пустой процесс
пустой процесс — это валидный CCS-процесс
действие
процесс может совершать действие и продолжиться как процесс
идентификатор процесса
пишем для использования идентификатора , чтобы ссылаться на процесс
выбор
процесс может продолжаться либо как , либо как
параллельная композиция
процессы и , существующие одновременно
переименование
процесс с действиями переименованными в
ограничение
процесс без действия

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

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

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

Модели, которые используются в изучении 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
  1. // Formal Methods for Performance Evaluation (англ.) / Herzog, Ulrich. — Springer, 2007. — Vol. 4486. — P. 318—370. — (Lecture Notes in Computer Science). — doi : .
Источник —

Same as Исчисление взаимодействующих систем