Universality of the chip-firing game

Goles, E.; Margenstern M.

Keywords: simulation, graph, universality, numerical, computer, theory, chip, shift, game, methods, firing, problem, Iterative, registers, Reachability

Abstract

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.

Más información

Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 172
Número: 1-2
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 1997
Página de inicio: 121
Página final: 134
URL: http://www.scopus.com/inward/record.url?eid=2-s2.0-0031074031&partnerID=q2rCbXpz