Asynchronous mappings and asynchronous cellular automata
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.
- Weighted asynchronous cellular automata
- An extension of Kleene's and Ochmański's theorems to infinite traces
- Asynchronous automata versus asynchronous cellular automata
- Deterministic asynchronous automata for infinite traces
- On the complementation of asynchronous cellular Büchi automata
- The monadic second-order logic of graphs. X: Linear orderings
- Asynchronous cellular automata for pomsets
- Resource traces: A domain for processes sharing exclusive resources.
- Computation by asynchronously updating cellular automata
- Distributed automata in an assumption-commitment framework
- Bounded time-stamping in message-passing systems
- Regular sets of infinite message sequence charts
- A study on delay-sensitive cellular automata
- Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
- A model for learning the news in social networks
- Time-stamps for Mazurkiewicz traces.
- Asynchronous sliding block maps
- Distributed Asynchronous Automata
- On Distributed Monitoring and Synthesis
- ON ASYNCHRONOUS CELLULAR AUTOMATA
- Automated synthesis of distributed controllers
- MSO Logic for Unambiguous Shared-Memory Systems
- Semantics of Deterministic Shared-Memory Systems
- Unambiguous shared-memory systems
- A quadratic construction for Zielonka automata with acyclic communication structure
- Asynchronous sliding block maps
- scientific article; zbMATH DE number 1759634 (Why is no real title available?)
- Determinizing asynchronous automata
- On the complementation of Büchi asynchronous cellular automata
- ASYNCHRONOUS AUTOMATA NETWORKS CAN EMULATE ANY SYNCHRONOUS AUTOMATA NETWORK
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- Pattern matching in trace monoids (extended abstract)
- Keeping track of the latest gossip in a distributed system
- Asynchronous cellular automata for infinite traces
- A framework for synthesis of communicating decentralised supervisors for discrete-event systems
- Fundamentals of Computation Theory
- Compositional synthesis of asynchronous automata
- A survey of cellular automata: types, dynamics, non-uniformity and applications
- Asynchronous cellular automata for pomsets without auto-concurrency
- A note on skew-asynchronous cellular automata
- Basic notions of universal algebra for language theory and graph grammars
- Local testability from words to traces, a suitable definition
- On synthesis of distributed monitors (invited talk)
- Synthesising asynchronous automata from fair specifications
- From trees to tree-like: distribution and synthesis for asynchronous automata
This page was built for publication: Asynchronous mappings and asynchronous cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690237)
