Исчисление взаимодействующих систем: различия между версиями
Animist (обсуждение | вклад) Создание заготовки статьи |
(нет различий)
|
Версия от 12:50, 25 марта 2010
Исчисление общающихся систем (англ. Calculus of Communicating Systems, CCS) — это исчисление процессов, введённое Робином Милнером около 1980, и название его книги, описывающей это исчисление. Исчисление работает с моделью неразделяемых коммуникаций между ровно двумя участниками. Формальный язык включает примитивы для описания параллельной композиции, выбора между действиями и рамки ограничений. CCS полезен для оценки качественной корректности свойств таких систем как deadlock или livelock.[1]
Согласно Милнеру, «Нет ничего канонического в выборе базовых комбинаторов, даже несмотря на то, что они были выбраны с большим вниманием к экономии. То, что характеризует наше исчисление, это не точный выбор комбинаторов, но выбор интерпретации и математической структуры».
Выражения языка интерпретируются как помеченная переходная система. Между этими моделями взаимное подобие используется как семантическая эквивалентность.
Синтаксис
Для данного множества имён действий, множество CCS-процессов определяется следующей грамматикой Бэкуса — Наура:
Части синтаксиса в данном выше порядке:
- пустой процесс
- пустой процесс — это валидный CCS-процесс
- действие
- процесс может совершать действие и продолжиться как процесс
- идентификатор процесса
- пишем для использования идентификатора , чтобы ссылаться на процесс
- выбор
- процесс can proceed either as the process or the process
- параллельная композиция
- процессы и , существующие одновременно
- переименование
- процесс с действиями переименованными в
- ограничение
- процесс без действия
Схожие исчисления и модели
- Общающиеся последовательные процессы (CSP) — язык, разработанный Энтони Хоаром,который появился в тоже время, что и CCS.
- Пи-исчисление, разработанное Милнером в конце 80-х, предоставляет подвижность коммуникационных звеньев, позволяя процессам собщать имена самих коммуникационных каналов.
- Алгебра процессов PEPA, разработанная Джейн Хиллстон, вводит время действия и вероятностный выбор, позволяя вычислять метрики производительности.
Некоторые языки, основанные на 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-131-15007-3. 1989
- ↑ Tackling Large State Spaces in Performance Modelling // Formal Methods for Performance Evaluation. — Springer, 2007. — Vol. 4486. — P. 318–370. — doi:10.1007/978-3-540-72522-0.
Это заготовка статьи по информатике. Помогите Википедии, дополнив её. |