Abelian networks. I: Foundations and examples
From MaRDI portal
Publication:2804993
DOI10.1137/15M1030984zbMATH Open1356.68072OpenAlexW2963037235MaRDI QIDQ2804993FDOQ2804993
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 \(\mathbb 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)- Infinite-step stationarity of rotor walk and the wired spanning forest
- How far do activated random walkers spread from a single source?
- Flat Holonomies on Automata Networks
- Abelian networks IV. Dynamics of nonhalting networks
- Essential enhancements in abelian networks: continuity and uniform strict monotonicity
- Non-fixation for conservative stochastic dynamics on the line
- Uniform threshold for fixation of the stochastic sandpile model on the line
- Laplacian growth and sandpiles on the Sierpiński gasket: limit shape universality and exact solutions
- The abelian distribution
- Abelian networks. III: The critical group
- Universality conjectures for activated random walk
- Absorbing-state phase transition and activated random walks with unbounded capacities
- On the complexity of the chip-firing reachability problem
- Chip-firing based methods in the Riemann-Roch theory of directed graphs
- Abelian oil and water dynamics does not have an absorbing-state phase transition
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- Abelian networks. II: Halting on all inputs
- Bootstrap percolation, and other automata
- Abelian logic gates
- Active phase for activated random walk on \(\mathbb{Z}\)
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- Rotor-routing reachability is easy, chip-firing reachability is hard
- Some halting problems for abelian sandpiles are undecidable in dimension three
- Cuts and flows of cell complexes
- Sandpiles on the square lattice
- Recurrence of horizontal-vertical walks
- Sorting via chip-firing
- CoEulerian graphs
- A five-element transformation monoid on labelled trees
- Random walks with local memory
- Sorting via chip-firing
- Hyperedge channels are abelian
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)
