ON SYNCHRONIZATION LANGUAGES
Lin Guo, Kai Salomaa, S. Yu · Fundamenta Informaticae · 1996
New constructs for synchronization termed synchronization expressions (SEs) have been developed as high-level language constructs for parallel programming languages [8, 9]. Statements that are constrained by certain synchronization requirements are tagged, and synchronization requests are specified as expressions of statement tags. In this paper, we introduce a new family of languages named synchronization languages which we use to give a precise semantic description for SEs. Under this description, relations such as equivalence and inclusion between SEs can be easily understood and tested. In practice, it also provides us with a systematic way for the implementation as well as the simplification of SEs in parallel programming languages. We show that each synchronization language is closed under the following rewriting rules: (1) a s b s → b s a s , (2) a t b t → b t a t , (3) a s b t → b t a s , (4) a t a s b t b s → b t b s a t a s and also h(a t a s b t b s ) → h(b t b s a t a s ) for any morphism h that satisfies certain conditions which will be specified in the paper. We conjecture that closure under the above rewriting rules is a sufficient condition for a regular st-language to be a synchronization language. Several other properties of synchronization languages are also studied.