Abelian networks. I: Foundations and examples
From MaRDI portal
Publication:2804993
DOI10.1137/15M1030984zbMATH Open1356.68072arXiv1309.3445OpenAlexW2963037235MaRDI QIDQ2804993FDOQ2804993
Authors: Benjamin Bond, Lionel Levine 
Publication date: 9 May 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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".
Full work available at URL: https://arxiv.org/abs/1309.3445
Recommendations
finite automatarotor walkabelian distributed processorsasynchronous computationleast action principlelocal-to-global principlechip-firingmonotone integer program
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Integer programming (90C10) Dynamical aspects of cellular automata (37B15)
Cites Work
- Title not available (Why is that?)
- Chip-firing and the critical group of a graph
- The sand-pile model and Tutte polynomials
- Self-organized critical state of sandpile automaton models
- Chip-firing games on graphs
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- Simulating a Random Walk with Constant Error
- CoEulerian graphs
- Rotor walks and Markov chains
- Chip-Firing and Rotor-Routing on Directed Graphs
- Trees, parking functions, syzygies, and deformations of monomial ideals
- Abelian networks. III: The critical group
- Fast simulation of large-scale growth models
- Generalized loop‐erased random walks and approximate reachability
- Abelian networks. II: Halting on all inputs
- Stabilizability and percolation in the infinite volume sandpile model
- Patterns formed by addition of grains to only one site of an Abelian sandpile
- Convergence of the abelian sandpile
- Title not available (Why is that?)
- Growth rates and explosions in sandpiles
- Pattern formation in growing sandpiles with multiple sources or sinks
- A family of bijections between \(G\)-parking functions and spanning trees
- Absorbing-state phase transition for driven-dissipative stochastic dynamics on \(\mathbb Z\)
- Activated random walkers: facts, conjectures and challenges
- The spread of a rumor or infection in a moving population
- A shape theorem for the spread of an infection
- On the complexity of integer programming
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Excited random walk
- Proof of Straley's argument for bootstrap percolation.
- The computational complexity of sandpiles
- Universality of the chip-firing game
- Title not available (Why is that?)
- Chip-Firing Games on Mutating Graphs
- Reflection processes on graphs and Weyl groups
- Local-to-global principles for the hitting sequence of a rotor walk
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- On the complexity of sandpile critical avalanches
- Rotor-router aggregation on the layered square lattice
- Rotor-router aggregation on the comb
- Oil and water: a two-type internal aggregation model
- Complexity of finite semigroups
- Distributed Computation for Linear Programming Problems Satisfying a Certain Diagonal Dominance Condition
- Source reversal and chip firing on graphs
- Rotor-Routing and Spanning Trees on Planar Graphs
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- A natural stochastic extension of the sandpile model on a graph
- Proportionate growth in patterns formed in the rotor-router model
- Discrete analog computing with rotor-routers
Cited In (32)
- 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
- Bootstrap percolation, and other automata
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- Recurrence of horizontal-vertical walks
- Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three
- Flat Holonomies on Automata Networks
- On the complexity of the chip-firing reachability problem
- Abelian networks. II: Halting on all inputs
- Essential enhancements in abelian networks: continuity and uniform strict monotonicity
- Uniform threshold for fixation of the stochastic sandpile model on the line
- Fast simulation of large-scale growth models
- 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
- Abelian networks IV. Dynamics of nonhalting networks
- Abelian Logic Gates
- Active phase for activated random walk on \(\mathbb{Z}\)
- Sorting via chip-firing
- 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
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)
