Universality of the parallel chip-firing game and related results

E. GOLES, M. MARGENSTERN

IBP-Litp 1995/33: 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

Résumé : Nous démontrons que les jeux à jetons sur des graphes non-orientés sont universels. Dans ce but, nous simulons n'importe quelle machine donnée à deux registres par des configurations de jeux à jetons. Comme corrollaires, nous démontrons que pour les graphes finis, il existe un temps de transition exponentiel pour atteindre une configuration périodique éventuellement exponentielle. Nous démontrons également que, pour les graphes infinis, le problème de l'arrêt sur une configuration donnée est indécidable.

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