Fri 10 Oct
Resource Based Models for Asynchrony
We propose a new graph-based approach to modelling asynchronous
languages and show how the new model can be viewed as a collapse of
the standard transition system model for asynchronous behaviour by
utilising the commuting properties of asynchronous transitions.
The motivation behind these new models stems from the issue of
regularity for asynchronous processes. We note that the class of
regular processes fails to contain many useful asynchronous processes
and we identify a larger subclass of BPP accordingly. We call this new
class `asynchronously regular processes'.
Using the new models we provide two appealing abstract
characterisations of asynchronous bisimulation equivalence, namely, as
spans of open maps and as a winning strategies for a bisimulation
game. Also, by exploiting the coincidence of finite graphs with
regular processes we see that bisimulation is polynomial time
decidable over our class of asynchronously regular processes.