COMPUTATION RESEARCH in BOSTON and BEYOND (CRiBB)

DateOct. 7, 2011
Speaker Lionel Levine (Massachusetts Institute of Technology)
TopicAbelian Networks
Abstract: Abelian networks are systems of communicating finite automata with a strong convergence property: the output of the network does not depend on the order in which the automata process their inputs. An example is the famous abelian sandpile model in statistical physics.

This talk will touch on three basic themes:

1.  Local-to-global principles: certain features of the automata are automatically inherited by the whole network.

2.  Critical group: a finite abelian group that governs the long-term behavior of the network.

3.  Halting problem: how to tell whether an abelian network halts on all inputs.

Joint work with James Propp (U. Mass Lowell) and with MIT undergraduates Ben Bond, Giuliano Giacaglia and Linda Zayas-Palmer.



back