Abelian networks. I: Foundations and examples
From MaRDI portal
Publication:2804993
Abstract: In Deepak Dhar's model of abelian distributed processors, automata occupy the vertices of a graph and communicate via the edges. We show that two simple axioms ensure that the final output does not depend on the order in which the automata process their inputs. A collection of automata obeying these axioms is called an "abelian network". We prove a least action principle for abelian networks. As an application, we show how abelian networks can solve certain linear and nonlinear integer programs asynchronously. In most previously studied abelian networks, the input alphabet of each automaton consists of a single letter; in contrast, we propose two non-unary examples of abelian networks: "oil and water" and "abelian mobile agents".
Recommendations
Cites work
- scientific article; zbMATH DE number 5764860 (Why is no real title available?)
- scientific article; zbMATH DE number 1256746 (Why is no real title available?)
- scientific article; zbMATH DE number 218327 (Why is no real title available?)
- A family of bijections between \(G\)-parking functions and spanning trees
- A natural stochastic extension of the sandpile model on a graph
- A shape theorem for the spread of an infection
- Abelian networks. II: Halting on all inputs
- Abelian networks. III: The critical group
- Absorbing-state phase transition for driven-dissipative stochastic dynamics on Z
- Activated random walkers: facts, conjectures and challenges
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- Chip-Firing Games on Mutating Graphs
- Chip-Firing and Rotor-Routing on Directed Graphs
- Chip-firing and the critical group of a graph
- Chip-firing games on graphs
- CoEulerian graphs
- Complexity of finite semigroups
- Convergence of the abelian sandpile
- Discrete analog computing with rotor-routers
- Distributed Computation for Linear Programming Problems Satisfying a Certain Diagonal Dominance Condition
- Excited random walk
- Generalized loop-erased random walks and approximate reachability
- Growth rates and explosions in sandpiles
- Local-to-global principles for the hitting sequence of a rotor walk
- Oil and water: a two-type internal aggregation model
- On the complexity of integer programming
- On the complexity of sandpile critical avalanches
- Pattern formation in growing sandpiles with multiple sources or sinks
- Patterns formed by addition of grains to only one site of an Abelian sandpile
- Proof of Straley's argument for bootstrap percolation.
- Proportionate growth in patterns formed in the rotor-router model
- Reflection processes on graphs and Weyl groups
- Rotor walks and Markov chains
- Rotor-router aggregation on the comb
- Rotor-router aggregation on the layered square lattice
- Rotor-routing and spanning trees on planar graphs
- Self-organized critical state of sandpile automaton models
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Simulating a Random Walk with Constant Error
- Source reversal and chip firing on graphs
- Stabilizability and percolation in the infinite volume sandpile model
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- The computational complexity of sandpiles
- The sand-pile model and Tutte polynomials
- The spread of a rumor or infection in a moving population
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- Trees, parking functions, syzygies, and deformations of monomial ideals
- Universality of the chip-firing game
Cited in
(32)- The abelian distribution
- Random walks with local memory
- A five-element transformation monoid on labelled trees
- Abelian oil and water dynamics does not have an absorbing-state phase transition
- Non-fixation for conservative stochastic dynamics on the line
- Sandpiles on the square lattice
- Cuts and flows of cell complexes
- Infinite-step stationarity of rotor walk and the wired spanning forest
- Abelian networks. III: The critical group
- Abelian logic gates
- Bootstrap percolation, and other automata
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- Recurrence of horizontal-vertical walks
- Abelian networks. II: Halting on all inputs
- Flat Holonomies on Automata Networks
- On the complexity of the chip-firing reachability problem
- Essential enhancements in abelian networks: continuity and uniform strict monotonicity
- Uniform threshold for fixation of the stochastic sandpile model on the line
- Sorting via chip-firing
- Universality conjectures for activated random walk
- Absorbing-state phase transition and activated random walks with unbounded capacities
- How far do activated random walkers spread from a single source?
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- Hyperedge channels are abelian
- Rotor-routing reachability is easy, chip-firing reachability is hard
- CoEulerian graphs
- Some halting problems for abelian sandpiles are undecidable in dimension three
- Abelian networks IV. Dynamics of nonhalting networks
- Active phase for activated random walk on \(\mathbb{Z}\)
- Laplacian growth and sandpiles on the Sierpiński gasket: limit shape universality and exact solutions
- Chip-firing based methods in the Riemann-Roch theory of directed graphs
- Sorting via chip-firing
This page was built for publication: Abelian networks. I: Foundations and examples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804993)
