A format for semantic equivalence comparison

✍ Scribed by Vashti Galpin

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 493 KB
• Volume: 309
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00129-4

✦ Synopsis

This paper presents a new format for process algebras, the extended tyft/tyxt format which generalises the tyft/tyxt format of Groote and Vaandrager. The format di ers from most previous formats in that the labels on transitions are treated as many-sorted terms. Bisimulation is a congruence for all operators deÿned by extended transition system speciÿcations in this format.

When one extended transition system speciÿcation is summed with another, the resulting bisimulation can either identify more terms (an abstracting extension up to bisimulation) or fewer terms (a reÿning extension up to bisimulation) than the original bisimulation on the individual system. The notions of abstracting extension and reÿning extension are deÿned, and two theorems are presented giving conditions required for achieving each type of extension. These results provide a way to compare di erent semantic equivalences deÿned for di erent process algebras.

Finally, an application of this theory to semantic equivalence comparison is given for a new result relating Castellani's pomset equivalence and Krishnan's multiprocessor equivalence.