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 unifies many approaches to modeling distributed systems such as the models of asynchronous trace automata and communicating finite-state machines. As a byproduct, we exhibit classes of pomsets and dags for which the radius of graph acceptors can be reduced to 1.
展开▼
