About Synchronization Languages (Full Version)

Synchronization languages are a model used to describe the behaviors of distributed applications whose synchronization constraints are expressed by synchronization expressions. Synchronization languages were conjectured by Guo, Salomaa and Yu to be characterized by a rewriting system. We have shown that this conjecture is not true. This negative result has led us to extend the rewriting system and Salomaa and Yu to extend the definition of synchronization languages. The aim of this paper is to establish the link between these two extensions, we show that the behaviors expressed by the two families of synchronization languages are only separated by morphisms. 1 Introduction Synchronization languages, introduced in [5], are regular languages which correspond to synchronization expressions introduced by Govindarajan, Guo, Yu and Wang [4] within the framework of the ParC project. These expressions allow a programmer to express minimal synchronization constraints of a program in a distribu..