zbMATH — the first resource for mathematics

Bisimilarity congruences for open terms and term graphs via tile logic. (English) Zbl 0999.68142
Palamidessi, Catuscia (ed.), CONCUR 2000 - Concurrency theory. 11th international conference, University Park, PA, USA, August 22-25, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1877, 259-274 (2000).
Summary: The definition of SOS formats ensuring that bisimilarity on closed terms is a congruence has received much attention in the last two decades. For dealing with open terms, the congruence is usually lifted from closed terms by instantiating the free variables in all possible ways; the only alternatives considered in the literature are Larsen and Xinxin’s context systems and Rensink’s conditional transition systems. We propose an approach based on the logic, where closed and open terms are managed uniformly, and study the ‘bisimilarity as congruence’ property for several the formats, accomplishing different concepts of open system.
For the entire collection see [Zbl 0944.00069].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)