n South African Computer Journal - Algebraic results for structured operational semantics

Volume 2000, Issue 26
  • ISSN : 1015-7999
  • E-ISSN: 2313-7835



This paper presents algebraic results that are important for the extended tyft/tyxt format [12, 13] which can be used to describe many different process algebras. This format is based on a many-sorted signature which permits both processes and labels to be treated syntactically. Existing results for this format permit the comparison of process algebra semantic equivalences by forming the sum of two transition system specifications and imposing certain conditions. the results presented in this paper involve the summing of congruences that model the actual process algebra labels, and determine under what conditions these congruences have important properties such as compatibility and conservativity. the aim of this paper is to show that the notion of sort-similarity on the sum of signatures is sufficient for the sum of the congruences induced by each label algebra to be the same as the congruence induced by the summed label algebras. Additionally, sort-similarity is sufficient for compatibility and conservativity when summing. Finally, conditions on the label algebra are given that ensure compatibility.

Loading full text...

Full text loading...


Article metrics loading...


This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error