Fairness of Components in System Computations

Theor. Comp. Sci. 356 (2006) 291 – 324 DOI: 10.1016/j.tcs.2006.02.011

In this paper we provide a simple characterization of (weak) fairness of components as defined by Costa and Stirling. The study is carried out at system specification level by resorting to a common process description language. This paper follows and exploits similar techniques as those developed in an earlier paper -- where fairness of actions was taken into account and was contrasted to the PAFAS timed operational semantics -- but the characterization of fair executions is based on a new semantics for PAFAS; it makes use of onlyww two copies of each basic action instead of infinitely many as and allows for a simple and finite representation of fair executions by using regular expressions.

The new semantics can also be understood as describing timed behaviour of systems with upper time bounds. The paper discusses in detail how this new semantics differs from the old one, and why theses changes are necessary to properly capture fairness of components.

Links:

• Tech. Rep. 2005-03