SYNCHRONIZATION EXPRESSIONS WITH EXTENDED JOIN OPERATION

Synchronization expressions are high level constructs used for specify ing minimal synchronization constraints of parallel processes. Their s emantics is defined by the corresponding synchronization language. The original definition of synchronization expressions [12, 13] forces th e languages to be closed under rewriting rules that, for instance, do not preserve regularity. Here we propose an extension of the syntactic definition of synchronization expressions, and an appropriate modific ation of their semantics. The extended definition has the advantage th at it allows us to eliminate the less well motivated transformations ( rewriting rules) describing properties of synchronization languages. W e show that the modified rewriting rules preserve regularity of the la nguages. Also, we obtain a characterization of finite synchronization languages as the family consisting of languages satisfying the start-t ermination property and closed under three types of simple rewriting r ules. (C) 1998-Elsevier Science B.V. All rights reserved.