통신 시스템의 미적분학

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "통신 시스템의 계산" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2011년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

통신시스템 미적분학(CCS)은 1980년경 로빈 밀너가 도입한 프로세스 미적분학이며 미적분을 기술한 책의 제목이다.그것의 행동은 정확히 두 참가자 사이의 분리할 수 없는 의사소통을 모델화한다.형식 언어에는 병렬 구성, 동작과 범위 제한 사이의 선택, 설명에 대한 원시 요소가 포함된다.CCS는 교착상태나 라이브록과 같은 시스템의 성질의 정확성을 평가하는 데 유용하다.^[1]

밀너에 따르면, "경제에 큰 관심을 가지고 선택되었음에도 불구하고, 기본적인 콤비네이터들의 선택에 대해 표준적인 것은 없다.우리의 미적분을 특징짓는 것은 결합자의 정확한 선택이 아니라 해석의 선택과 수학적 틀의 선택이다."

그 언어의 표현은 라벨이 붙은 과도체제로 해석된다.이 모델들 사이에서, 이등비례는 의미적 동등성으로 사용된다.

구문

일련의 행동 명칭을 부여하면, CCS 프로세스 세트는 다음과 같은 BNF 문법에 의해 정의된다.

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

구문의 부분은 위에 주어진 순서에 따른다.

비활동적인 과정

비활성 프로세스 $0{\displaystyle \mathrm{}}$ ${\displaystyle 0}$은(는) 유효한 CCS 프로세스임

액션

${\displaystyle {a\mathrm{}}_{}.}$ ${\displaystyle {}_{}}$ 1$[\$의 과정$P_{1}:{$1}은(는) ${\displaystyle$ a$} 작업$을 수행하고 프로세스 ${\displaystyle {P\mathrm{}}_{}}$ 1$${\$displaystyle P_{$1}로 계속 진행할$$ 수 있다.

프로세스 식별자

write ${\displaystyle A{\overset {\underset {\mathrm {def} }{}}{=}}P_{1}}$ to use the identifier ${\displaystyle A}$ to refer to the process ${\displaystyle P_{1}}$ (which may contain the identifier ${\displaystyle A}$ itself, i.e., recursive definitions are allowed)

합계

프로세스 $P{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$+ ${\displaystyle {P\mathrm{}}_{}}$ 2 ${\$}}: ${\displaystyle {프로세스\mathrm{}}_{}}$ P 1 ${\$1}, ${\displaystyle {프로세스\mathrm{}}_{}}$ P$$2 {\$displaystyle P_{2$} 중 하나로 진행할 수 있다$$.

평행 구성

${\displaystyle P_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle P{}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$2}}: $P{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}와$$ P ${\displaystyle {2\mathrm{}}_{}}$ ${\$2}} 공정들이 $동시$에 존재함을$$$$ 알려준다$.$

이름 바꾸기

${\displaystyle P_{}}$ ${\displaystyle {1\mathrm{}}_{}}$[ ${\displaystyle b}$/ ${\displaystyle a}$ ${\displaystyle ]}$ ${\displaystyle P_{1}[b/a]}$은(는) 프로세스 $P{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}이며$$, 이름이$$ ${\displaystyle a}$인 모든 작업은 b ${\displaystyle$ b$}(으$)로 이름이$$ 변경된다.

제한

${\displaystyle {}_{}P}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}\mathrm{}}$ ${\displaystyle$ $P_${$1}{\backslash$ }a$}은($는$)$ 동작이 $없는$ P ${\displaystyle {1\mathrm{}}_{}}$ ${\$$displaystyle$ $P_{$1} $공정$이다$.$

관련 캘커리, 모델 및 언어

• 토니 호어(Tony Hoare)가 개발한 순차적 프로세스 커뮤니케이션(CSP)은 CCS와 비슷한 시기에 생겨난 정식 언어다.
• 통신 프로세스 대수(ACP)는 1982년 얀 버그스트라와 얀 윌렘 클롭에 의해 개발되었으며, CCS와 유사한 종류의 프로세스에 대해 추론하기 위해 공리적인 접근방식(유니버설 대수학 스타일)을 사용한다.
• 80년대 후반 로빈 밀너, 요아힘 파로, 데이비드 워커가 개발한 파이-미적분은 통신 채널의 명칭을 프로세스가 직접 통신할 수 있도록 함으로써 통신 링크의 이동성으로 CCS를 확장한다.
• 제인 힐스턴이 개발한 PEPA는 기하급수적으로 분산된 비율과 확률적 선택 측면에서 활동 타이밍을 도입해 성과 지표를 평가할 수 있게 했다.
• 빈센트 다노스, 장 크리빈 등이 도입한 가역 통신 동시 시스템(RCCS)은 CCS 프로세스 실행에 (부분적) 가역성을 도입한다.

CCS 기반 다른 언어:

• 방송 시스템의 미적분학
• LOTOS(Language Of Time Order Specification)
• PALPS(Process Miculus for Spacely-Expective Ecology Models)는 CCS의 확장으로, 위치에^[2] 대한 확률론적 선택, 위치 및 속성이 있다.
• Java 오케스트레이션 언어 인터프리터 엔진(Jolie)^[3]

CCS 유사 시스템 연구에 사용된 모델:

• 히스토리 모노이드
• 배우 모델

참조

• 로빈 밀너: 의사소통 시스템의 미적분학, 스프링거 버랙, ISBN0-387-10235-3. 1980.
• 로빈 밀너, 통신 및 동시성, 프렌티스 홀, 컴퓨터 사이언스 인터내셔널 시리즈, ISBN 0-13-115007-3. 1989