On the Expressiveness of Asynchronous Cellular Automata

Abstract. We show that a slightly extended version of asynchronous cellular automata, relative to any class of pomsets and dags without au-toconcurrency, has the same expressive power as the existential fragment of monadic second-order logic. In doing so, we provide a framework that uni es many approaches to modeling distributed systems such as the models of asynchronous trace automata and communicating nite-state machines. As a byproduct, we exhibit classes of pomsets and dags for which the radius of graph acceptors can be reduced to 1.