Hierarchy of Asynchronous Automata

AbstractWe study a natural notion of communication structure associated with asynchronous automata: we characterize which transition systems are isomorphic to an asynchronous automaton w.r.t. a given communication structure. For that, we present an algorithm to split global states into local states of communicating processes, similar to the regional technique for the synthesis problem of Petri nets. Our main result is an axiomatic criterion for the communication structures which decompose the same class of transition systems; this allows us to characterize and compare several particular classes of asynchronous automata. An immediate corollary of this study is a generic extension of Zielonka's theorem. We finally apply this method to asynchronous automata which describe systems of processes that communicate through shared memories