Universality of the chip-firing game

Eric Goles, Maurice Margenstern

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


We prove that the parallel updating of the chip-firing game on undirected graphs is universal. To achieve that, we simulate any given two-register machine by chip configurations. As corollaries, we prove that for finite graphs there exists exponential transient time to reach periodic configurations as well as exponential cycles. Also, we prove, for infinite graphs, that the reachability problem is undecidable.

Original languageEnglish
Pages (from-to)121-134
Number of pages14
JournalTheoretical Computer Science
Issue number1-2
StatePublished - 10 Feb 1997
Externally publishedYes


Dive into the research topics of 'Universality of the chip-firing game'. Together they form a unique fingerprint.

Cite this