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.