Synchronization languages
Synchronization expressions introduced in [7] within the framework of the ParC 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 associated 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 synchronization constraints expressed by the programmer with synchronization expressions. So these languages describe all the correct executions of a program. In [9, 10] Guo, Salomaa and Yu propose a characterization of synchronization languages based on a rewriting system named R which generalizes partial commutations. This system gives a way to rewrite a word representing a parallel execution into a word with a lower or equal degree of parallelism. Guo et 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 closed under R to be a synchronization language. We show that the conjecture is true in the particular case of languages expressing 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.
rewriting systems regular languages concurrency