Descriptive power of synchronized shuffle expressions
Hirotaka Uoi, Toshiro Araki, Nobuki Tokura · Systems and Computers in Japan · 1987
Abstract As a model to describe the concurrent system with a synchronization mechanism, Holenderski has proposed the synchronized shuffle expression (SSE). SSE is a shuffle expression obtained by adding a synchronized shuffle operator with its closure and projection operator. This paper considers various subclasses of SSE. It is shown that the class of languages represented by the subclass excluding the projection operator is the same as the class of recursively enumerable languages. The hierarchical relations among the subclasses are described.