Abelian Networks I. Foundations and Examples
From MaRDI portal
Publication:2804993
DOI10.1137/15M1030984zbMath1356.68072arXiv1309.3445OpenAlexW2963037235MaRDI QIDQ2804993
Publication date: 9 May 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.3445
least action principlefinite automatarotor walkabelian distributed processorsasynchronous computationlocal-to-global principlechip-firingmonotone integer program
Integer programming (90C10) Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Dynamical aspects of cellular automata (37B15)
Related Items (30)
Laplacian growth and sandpiles on the Sierpiński gasket: limit shape universality and exact solutions ⋮ Abelian networks. III: The critical group ⋮ Abelian networks IV. Dynamics of nonhalting networks ⋮ Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three ⋮ Uniform threshold for fixation of the stochastic sandpile model on the line ⋮ Bootstrap percolation, and other automata ⋮ Abelian sandpile model and Biggs-Merino polynomial for directed graphs ⋮ Non-fixation for conservative stochastic dynamics on the line ⋮ Chip-firing based methods in the Riemann-Roch theory of directed graphs ⋮ Recurrence of horizontal-vertical walks ⋮ Essential enhancements in abelian networks: continuity and uniform strict monotonicity ⋮ Universality conjectures for activated random walk ⋮ Abelian networks. II: Halting on all inputs ⋮ Active phase for activated random walk on \(\mathbb{Z}\) ⋮ Absorbing-state phase transition and activated random walks with unbounded capacities ⋮ Sandpiles on the square lattice ⋮ Sorting via chip-firing ⋮ Sorting via chip-firing ⋮ CoEulerian graphs ⋮ Random walks with local memory ⋮ Fast Simulation of Large-Scale Growth Models ⋮ Abelian Logic Gates ⋮ How far do activated random walkers spread from a single source? ⋮ A five-element transformation monoid on labelled trees ⋮ Rotor-routing reachability is easy, chip-firing reachability is hard ⋮ Infinite-step stationarity of rotor walk and the wired spanning forest ⋮ Abelian oil and water dynamics does not have an absorbing-state phase transition ⋮ Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle ⋮ On the complexity of the chip-firing reachability problem ⋮ Cuts and flows of cell complexes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Abelian networks. III: The critical group
- Absorbing-state phase transition for driven-dissipative stochastic dynamics on \(\mathbb Z\)
- Local-to-global principles for the hitting sequence of a rotor walk
- 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
- Chip-firing games on graphs
- Abelian networks. II: Halting on all inputs
- Growth rates and explosions in sandpiles
- Activated random walkers: facts, conjectures and challenges
- Pattern formation in growing sandpiles with multiple sources or sinks
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- Stabilizability and percolation in the infinite volume sandpile model
- Chip-firing and the critical group of a graph
- The computational complexity of sandpiles
- Universality of the chip-firing game
- The sand-pile model and Tutte polynomials
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Source reversal and chip firing on graphs
- Excited random walk
- A family of bijections between \(G\)-parking functions and spanning trees
- Reflection processes on graphs and Weyl groups
- Patterns formed by addition of grains to only one site of an Abelian sandpile
- Convergence of the abelian sandpile
- Proof of Straley's argument for bootstrap percolation.
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- A natural stochastic extension of the sandpile model on a graph
- The spread of a rumor or infection in a moving population
- A shape theorem for the spread of an infection
- Complexity of finite semigroups
- CoEulerian graphs
- Rotor Walks and Markov Chains
- Fast Simulation of Large-Scale Growth Models
- Proportionate growth in patterns formed in the rotor-router model
- Simulating a Random Walk with Constant Error
- Chip-Firing and Rotor-Routing on Directed Graphs
- On the complexity of integer programming
- Self-organized critical state of sandpile automaton models
- Trees, parking functions, syzygies, and deformations of monomial ideals
- Chip-Firing Games on Mutating Graphs
- Discrete analog computing with rotor-routers
- Rotor-Routing and Spanning Trees on Planar Graphs
- Generalized loop‐erased random walks and approximate reachability
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- Distributed Computation for Linear Programming Problems Satisfying a Certain Diagonal Dominance Condition
This page was built for publication: Abelian Networks I. Foundations and Examples
