Asynchronous mappings and asynchronous cellular automata (Q690237)

Asynchronous cellular automata are studied. They differ from usual cellular automata by decentralized control structure and by asynchronous performing of actions. Their behaviour is described by trace languages, subsets of partially commutative monoids. The main result concerning this class of automata states that they accept exactly all recognizable trace languages. A new notion of asynchronous mapping is introduced and it is shown that for a given asynchronous mapping, a corresponding asynchronous cellular automaton can be constructed. An example of nontrivial asynchronous mapping is given and two independent constructions of asynchronous mapping recognizing a given trace language are presented, both of them based on the example. Finally an application of the above mentioned asynchronous mapping is presented. It is a distributed system with agents communicating by means of messages left in boxes with bounded time-stamps.