The Expressive Power of Delay Operators in SCCS

Abstract

We investigate the relative expressive power of finite delay operators in SCCS. These were introduced by Milner and by Hennessy to study fairness properties of processes in the context of SCCS. We show that the context sensitive delay operator introduced by Hennessy is more expressive than the finite delay operator introduced by Milner. This result is closely related to recent results by Panangaden and Stark on the expressive power of fair merge in asynchronous dataflow (Kahn) networks. It indicates that the expressiveness results obtained there are not sensitive to the precise computational model since SCCS, unlike Kahn networks, is synchronous and permits expansion of recursively defined processes.