Kalkyl av interagerande system

Calculus of  Communicating Systems ( CCS ) inom datavetenskap är  en processkalkyl som utvecklades av Robin Milner 1980. Kalkylen arbetar med en modell av oskiljaktig kommunikation mellan exakt två deltagare. Det formella språket inkluderar primitiver för att beskriva parallell komposition, val mellan handlingar och begränsningsramar. CCS är användbart för att utvärdera den kvalitativa riktigheten av egenskaper som mutex eller " livelock " [1] .

Enligt Milner "finns det inget kanoniskt med valet av grundläggande kombinatorer, även om de har valts med stor omsorg för ekonomin. Det som kännetecknar vår kalkyl är inte det exakta valet av kombinatorer, utan valet av tolkning och matematisk struktur . ”

Språkuttryck tolkas som ett märkt transitivt system . Mellan dessa modeller används ömsesidig likhet som en semantisk ekvivalens.

Syntax

För en given uppsättning åtgärdsnamn definieras uppsättningen av CCS-processer av följande Backus-Naur-grammatik :

Delar av syntaxen, i den ordning som anges ovan:

tom process en tom process  är en giltig CCS-process handling en process kan vidta en åtgärd och fortsätta som en process process-ID skriv för att använda id för att referera till en process val processen kan fortsätta antingen som , eller som parallell komposition processer och som existerar samtidigt byta namn process med åtgärder bytt namn till begränsning process utan åtgärd

Relaterade kalkyler och modeller

• Calculus of interacting processes ( eng.  Communicating sequential processes ), CSP är ett språk utvecklat av Anthony Hoare , som dök upp samtidigt som CCS.
• Pi-calculus , utvecklad av Milner i slutet av 1980-talet, ger mobilitet för kommunikationslänkar genom att tillåta processer att rapportera namnen på själva kommunikationskanalerna.
• PEPA Process Algebra , utvecklad av Jane Hillston , introducerar handlingstid och probabilistiska val, vilket gör att prestandamått kan beräknas.

Några notationer baserade på CCS:

• Beräkning av sändningssystem ;  _
• LOTOS .

Modeller som används i studien av CCS-system:

• Historia monoid ;_ _ 
• Skådespelarens modell .

Länkar

• 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. ↑ Ta itu med stora tillståndsutrymmen i prestationsmodellering // Formella metoder för prestationsutvärdering  / Herzog, Ulrich. - Springer, 2007. - Vol. 4486. - S. 318-370. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-540-72522-0 .