Asynchronous mappings and asynchronous cellular automata (Q690237)

From MaRDI portal
Revision as of 20:25, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
scientific article
Language Label Description Also known as
English
Asynchronous mappings and asynchronous cellular automata
scientific article

    Statements

    Asynchronous mappings and asynchronous cellular automata (English)
    0 references
    0 references
    0 references
    0 references
    20 April 1994
    0 references
    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.
    0 references
    distributed systems
    0 references
    asynchronous cellular automata
    0 references
    trace languages
    0 references
    partially commutative monoids
    0 references
    0 references

    Identifiers