Finite Reresentations of CCS and TCSP Programs by Automata and Petri Nets

این کار به رویکردهای مختلف برای مدل‌سازی فرآیندهای موازی مربوط می‌شود. از یک طرف به اصطلاح "جبرهای فرآیندی" یا "زبان های برنامه نویسی انتزاعی" با حساب سیستم های ارتباطی میلنر (CCS) و نسخه نظری فرآیندهای متوالی ارتباطی Hoare (CSP) به عنوان نمایندگان اصلی وجود دارد. از سوی دیگر، مدل‌های ماشینی، یعنی خودکارهای حالت محدود کلاسیک (سیستم‌های انتقال) وجود دارند که، با این حال، مفاهیم متمایزتر از هم ارزی نسبت به برابری زبان‌ها برای آنها استفاده می‌شود. و ثانیا، انواع مختلفی از شبکه های پتری وجود دارد که به ترتیب شبکه های امن و عمومی (مکان/انتقال) و شبکه های محمول/ گذار هستند. در یک چارچوب یکسان، نحو و معنای عملیاتی CCS و TCSP توضیح داده شده است. ما هر دو را در نظر می گیریم، معناشناسی درهم تنیده معروف میلنر، که مبتنی بر سیستم های انتقال نامتناهی است، و همچنین معناشناسی توزیع شده جدید معرفی شده توسط دگانو و همکاران، که بر اساس شبکه های امن بی نهایت است. بخش اصلی این کار شامل سه ساختار مبتنی بر نحو از سیستم‌های انتقال، شبکه‌های امن و شبکه‌های محمول/ گذار است. هر یک از آنها با اثبات سازگاری همراه است. با توجه به محدودیت‌های ذاتی، که در اینجا نیز مورد بررسی قرار می‌گیرند، نه برای سیستم‌های انتقال و شبکه‌های محدود، و نه برای شبکه‌های عمومی، نمایش ثابت محدودی از همه برنامه‌های CCS و TCSP وجود ندارد. با این حال، زبان‌های فرعی که اجازه نمایش محدود را می‌دهند، قابل تشخیص هستند. از سوی دیگر ساخت شبکه های محمول/ گذار برای همه برنامه های CCS که در آن هر انتخاب و هر جسم بازگشتی به ترتیب شروع می شود امکان پذیر است.

This work relates different approaches for the modelling of parallel processes. On the one hand there are the so-called "process algebras" or "abstract programming languages" with Milner's Calculus of Communicating Systems (CCS) and the theoretical version of Hoare's Communicating Sequential Processes (CSP) as main representatives. On the other hand there are machine models, i.e. the classical finite state automata (transition systems), for which, however, more discriminating notions of equivalence than equality of languages are used; and secondly, there are differently powerful types of Petri nets, namely safe and general (place/transition) nets respectively, and predicate/transition nets. Within a uniform framework the syntax and the operational semantics of CCS and TCSP are explained. We consider both, Milner's well-known interleaving semantics, which is based on infinite transition systems, as well as the new distributed semantics introduced by Degano et al., which is based on infinite safe nets. The main part of this work contains three syntax-driven constructions of transition systems, safe nets, and predicate/transition nets respectively. Each of them is accompanied by a proof of consistency. Due to intrinsic limits, which are also investigated here, neither for transition systems and finite nets, nor for general nets does a finite consistent representation of all CCS and TCSP programs exist. However sublanguages which allow finite representations are discerned. On the other hand the construction of predicate/transition nets is possible for all CCS programs in which every choice and every recursive body starts sequentially.