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*:

An *automaton with concurrency relations* $(S,i,E,\mathrm{Tran},I)$ consists of

- a transition system $(S,i,E,\mathrm{Tran})$, such that whenever $(s,a,s\prime )$, and $(s,a,s\u2033)$ are in $\mathrm{Tran}$, then $s\prime =s\u2033$;

and

- $I=\{{I}_{s}\mid s\in S\}$ is a family of irreflexive, symmetric binary relations, ${I}_{s}$ on $E$ such that whenever ${a}_{1}{I}_{s}{a}_{2}$ (with ${a}_{1},{a}_{2}\in E$), 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 $\mathrm{Tran}$.

- Eric Goubault and Samuel Mimram, Formal Relationships Between Geometrical and Classical Models for Concurrency

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