nLab
asynchronous automaton

Asynchronous automata are a generalisation of both transition systems and Mazurkiewicz traces. Their study has influences other models for concurrency such as transition systems with independence (also called asynchronous transition systems). The idea is to decorate transition systems with an independence relation (much as in (Mazurkiewicz) trace alphabets) between actions that allow one to distinguish true concurrency from mutual exclusion (i.e. non-determinism). Following the paper by Goubault and Mimram, we use a slight modification called automata with concurrency relations:

Definition

An automaton with concurrency relations (S,i,E,Tran,I) consists of

  • a transition system (S,i,E,Tran), such that whenever (s,a,s), and (s,a,s) are in Tran, then s=s;

and

  • I={I ssS} is a family of irreflexive, symmetric binary relations, I s on E such that whenever a 1I sa 2 (with a 1,a 2E), there exist transitions (s,a 1,s 1), (s,a 2,s 2), (s 1,a 2,r), and (s 2,a 1,r) in Tran.

References

Revised on December 23, 2010 07:27:16 by Toby Bartels (173.190.146.220)