TY - JOUR
T1 - Universality of the chip-firing game
AU - Goles, Eric
AU - Margenstern, Maurice
PY - 1997/2/10
Y1 - 1997/2/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031074031&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(95)00242-1
DO - 10.1016/S0304-3975(95)00242-1
M3 - Article
AN - SCOPUS:0031074031
SN - 0304-3975
VL - 172
SP - 121
EP - 134
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -