Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Montanari, Ugo | Sassone, Vladimiro
Affiliations: Dipartimento di Informatica – Università di Pisa, Corso Italia 40 – 56125 – Pisa – Italy, E-mails: ugo@di.unipi.it, vladi@di.unipi.it
Note: [1] Research supported in part by HEWLETT-PACKARD Laboratories, Pisa Science Center.
Abstract: Weak Observational Congruence (woc) defined on CCS agents is not a bisimulation since it does not require two states reached by bisimilar computations of woc agents to be still woc, e.g. α.τ.β.nil and α.β.nil are woc but τ.β.nil and β.nil are not. This fact prevent us from characterizing CCS semantics (when τ is considered invisible) as a final algebra, since the semantic function would induce an equivalence over the agents that is both a congruence and a bisimulation. In the paper we introduce a new behavioural equivalence for CCS agents, which is the coarsest among those bisimulations which are also congruences. We call it Dynamic Observational Congruence because it expresses a natural notion of equivalence for concurrent systems required to simulate each other in the presence of dynamic, i.e. run time, (re)configurations. We provide an algebraic characterization of Dynamic Congruence in terms of a universal property of finality. Furthermore we introduce Progressing Bisimulation, which forces processes to simulate each other performing explicit steps. We provide an algebraic characterization of it in terms of finality, two logical characterizations via modal logic in the style of HML and a complete axiomatization for finite agents (consisting of the axioms for Strong Observational Congruence and of two of the three Milner’s τ-laws). Finally, we prove that Dynamic Congruence and Progressing Bisimulation coincide for CCS agents.
DOI: 10.3233/FI-1992-16206
Journal: Fundamenta Informaticae, vol. 16, no. 2, pp. 171-199, 1992
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl