Lionel Levine:
Abelian networks
Abstract
An abelian network is a collection of finite automata that
live at the vertices of a graph and communicate via the edges. It
produces the same output no matter in what order the automata process
their inputs. This talk will touch on three basic themes, using
chip-firing and rotor-routing as illustrating examples.
1. Halting problem: how to tell whether an abelian network halts on all inputs.
2. Local-to-global principles: certain features of the automata are
inherited by the whole network.
3. Critical group: a finite abelian group that governs the long-term
behavior of the network.