Rapport de Recherche Litp /
Litp research reports
17 pages - Juin/June 1995 - Document en anglais.
PostScript : Ko /Kb
Titre / Title: Universality of the parallel chip-firing game and related results
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 fnite graphs there exists exponential transient time to reach periodic configurations as well as exponential ones. Also, we prove, for infinite graphs, that the reachability problem is undecidable.
Publications internes Litp 1995 / Litp research reports 1995