n South African Computer Journal - Algebraic results for structured operational semantics
|Article Title||Algebraic results for structured operational semantics|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Publication Date||Nov 2000|
|Pages||13 - 21|
|Keyword(s)||Bisimulation, Comparison of semantic equivalences, D.3.1, Extended tyft / tyxt format, F.1.2, F.3.2, F.4.3, Many-sorted, Operational semantics, Process algebra and Sort-similar|
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.
Article metrics loading...