Synchronization languages

Synchronization expressions introduced in [7] within the framework of the P arC project are a high-level construct which allow a programmer to express minimal synchronization constraints of a program in a distributed context. The study and the implementation of these expressions are based on their as sociated synchronization languages. Synchronization languages have been introduced in [9, 10]. They give a way to implement synchronization expressions and specify their semantic. These languages represent distributed systems whose behaviour respects synchroniz ation constraints expressed by the programmer with synchronization expressi ons. So these languages describe all the correct executions of a program. I n [9, 10] Guo, Salomaa and Yu propose a characterization of synchronization languages based on a rewriting system named R which generalizes partial co mmutations. This system gives a way to rewrite a word representing a parall el execution into a word with a lower or equal degree of parallelism. Guo e t al. show that every synchronization language is closed under the system R and they conjecture that it is sufficient for a regular language to be clo sed under R to be a synchronization language. We show that the conjecture is true in the particular case of languages exp ressing the synchronization between two distinct actions. We also show that the conjecture is false in the general case. (C) 1999-Elsevier Science B.V , All rights reserved.