UNIVERSALITY OF THE CHIP-FIRING GAME

Authors
GOLES E MARGENSTERN M
Citation
E. Goles et M. Margenstern, UNIVERSALITY OF THE CHIP-FIRING GAME, Theoretical computer science, 172(1-2), 1997, pp. 121-134
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
172
Issue
1-2
Year of publication
1997
Pages
121 - 134
Database
ISI
SICI code
0304-3975(1997)172:1-2<121:UOTCG>2.0.ZU;2-D
Abstract
We prove that the parallel updating of the chip-firing game on undirec ted graphs is universal. To achieve that, we simulate any given two-re gister machine by chip configurations. As corollaries, we prove that f or finite graphs there exists exponential transient time to reach peri odic configurations as well as exponential cycles. Also, we prove, for infinite graphs, that the reachability problem is undecidable.