Page d'accueil du CNRS Page d'accueil de Paris Diderot Page d'accueil du LIAFA
LIAFA
Laboratoire d'Informatique Algorithmique: Fondements et Applications
CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014
75205 Paris Cedex 13 - Tél: +33(0)1.57.27.92.56 - Fax: +33(0)1.57.27.94.09
Page d'accueil de la fondation Sciences Mathématiques de Paris Page d'accueil de FRMPC
   Staff      Contact      How to get to LIAFA      Teaching      Webmail   


Version française

Research reports

  • Report number: 1995-056
  • Authors: E. GOLES, M. MARGENSTERN
  • Title: Universality of the parallel chip-firing game and related results
  • Summary:


     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 ones. Also, we prove, for infinite graphs, that the reachability problem is undecidable.


 
 ©  LIAFA 1995, Last updating: 2013, May webmestre[at]liafa.univ-paris-diderot.fr