CNRS Universit� de Marne-la-Vall�e
Institut Gaspard-Monge

Pierre Guillon

Publications
@STRING{igm_phddoc={Th\`ese de doctorat} } @STRING{igma_elsev={Elsevier} } @STRING{igma_mfcs={International Symposium on Mathematical Foundations of Computer Science} } @STRING{igma_shortlncs={LNCS} } @STRING{igma_spver={Springer-Verlag} } @STRING{igma_tcs= {Theoretical Computer Science} } @STRING{igmac_cie={Conference on Computability in Europe - Computation and Logic in the Real World} } @Article{ IGMA_DenGuiMas09, author = {Dennunzio, Alberto and Guillon, Pierre and Masson, Beno\^it}, title = {{Sand Automata as Cellular Automata}}, journal = igma_tcs, publisher = igma_elsev, year = {2009}, volume = {410}, number = {38-40}, pages = {3962--3974}, month = sep, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/saasca.pdf}, url = {http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4WJHBCC-1&_user=10&_coverDate=09%2F06%2F2009&_alid=983085139&_rdoc=2&_fmt=high&_orig=search&_cdi=5674&_sort=r&_docanchor=&view=c&_ct=4&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=bafacb5920c554690464a1cfb05549a6}, keywords = { sand automata, cellular automata, dynamical systems, nilpotency, undecidability}, lang = {EN}, note = { } } @Article{ IGMA_BliBlaHer07, idhal = {hal-00524054}, pwdhal = {5 @cn0?}, typeupe = {ARTICLE_international}, author = {Blin, Guillaume and Blais, Eric and Hermelin, Danny and Guillon, Pierre and Blanchette, Mathieu and El-Mabrouk, Nadia}, labs = {3210,,,3210,,}, title = {{{{Gene Maps Linearization using Genomic Rearrangement Distances}}}}, journal = {Journal of Computational Biology}, year = {2007}, volume = {14}, number = {4}, pages = {394--407}, pdf = {http://igm.univ-mlv.fr/~gblin/pdf/Blin_Blais_Hermelin_Guillon_Blanchette_ElMabrouk_JCB_2007.pdf}, lang = {EN}, note = { } } @InProceedings{ IGMA_GuiRic08, author = {Guillon, Pierre and Richard, Ga\'etan}, title = {{Nilpotency and Limit Sets of Cellular Automata}}, booktitle = {33rd } # igma_mfcs # { (MFCS'08)}, igmnumconf = {33}, igmnumbisconf = {rd}, igmacroconf = {MFCS}, igmconf = igma_mfcs, series = igma_shortlncs, publisher = {Springer Berlin / Heidelberg}, editor = {Ochma\'nski, Edward and Tyszkiewicz, Jerzy}, year = {2008}, volume = {5162}, pages = {375--386}, days = {25-29}, month = aug, address = {Toru\'n, Poland}, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/nilpult.pdf}, url = {http://www.springerlink.com/content/j744444182821102}, keywords = {, cellular automata, nilpotency, dynamical systems, attractors}, note = { } } @InProceedings{ IGMA_CerGui07, author = {Cervelle, Julien and Guillon, Pierre}, title = {{Towards a Rice Theorem on Traces of Cellular Automata}}, booktitle = {32th } # igma_mfcs # { (MFCS'07)}, igmnumconf = {32}, igmnumbisconf = {th}, igmacroconf = {MFCS}, igmconf = igma_mfcs, series = igma_shortlncs, publisher = igma_spver, editor = {Ku\vcera, Ludek and Ku\vcera, Anton\'in}, year = {2007}, volume = {4708}, pages = {310--319}, days = {26-31}, month = aug, address = {\vCesk\'y Krumlov, Czech Republic}, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/trice.pdf}, url = {http://www.springerlink.com/content/7318354x8tk602q1/?p=312d99b60b7445b49acdabfcfe563a0b%u03C0=0}, keywords = {discrete-time dynamical systems, cellular automata, symbolic dynamics, formal languages, computability, decidability}, note = { } } @InProceedings{ IGMA_CerForGui07, author = {Cervelle, Julien and Formenti, Enrico and Guillon, Pierre}, title = {{Sofic Trace of a Cellular Automaton}}, booktitle = {3rd } # igmac_cie # { (CiE'07)}, igmnumconf = {3}, igmnumbisconf = {rd}, igmacroconf = {CiE}, igmconf = igmac_cie, series = igma_shortlncs, publisher = igma_spver, editor = {Cooper, S. Barry and L\"owe, Benedict and Sorbi, Andrea}, year = {2007}, volume = {4497}, pages = {152--161}, days = {18-23}, month = jun, address = {Siena, Italy}, igmrefpreprint= {hal-00135811}, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/trace.pdf}, url = {http://www.springerlink.com/content/r371136036536783/?p=15347994b72748d689ae2d82c90de38d%u03C0=69}, slides = {http://www.mat.unisi.it/~sorbi/sito/CiETalks/guillon.pdf}, keywords = {discrete-time dynamical systems, cellular automata, symbolic dynamics, sofic systems, formal languages}, note = { hal-00135811 } } @InProceedings{ IGMA_DenGuiMas08b, author = {Dennunzio, Alberto and Guillon, Pierre and Masson, Beno\^it}, title = {{Stable Dynamics of Sand Automata}}, booktitle = {5th IFIP Conference on Theoretical Computer Science (TCS'08)}, igmnumconf = {5}, igmnumbisconf = {th}, igmacroconf = {TCS}, igmconf = {IFIP Conference on Theoretical Computer Science}, series = {International Federation for Information Processing}, publisher = {Springer Boston}, editor = {Ausiello, Giorgio and Karhum\"aki, Juhani and Mauri, Giancarlo and Ong, Luke}, year = {2008}, volume = {273}, pages = {157--169}, days = {8-10}, month = sep, address = {Milano, Italy}, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/stablesa.pdf}, url = {http://www.springerlink.com/content/3664858346412277}, keywords = { sand automata, dynamical systems, undecidability, nilpotency}, lang = {EN}, note = { } } @InProceedings{ IGMA_DenGuiMas08, author = {Dennunzio, Alberto and Guillon, Pierre and Masson, Beno\^it}, title = {{Topological Properties of Sand Automata as Cellular Automata}}, booktitle = {1st Symposium on Cellular Automata (JAC'08)}, igmnumconf = {1}, igmnumbisconf = {st}, igmacroconf = {JAC}, igmconf = {Symposium on Cellular Automata}, publisher = {MCCME Publishing House}, editor = {Durand, Bruno}, year = {2008}, pages = {216--227}, days = {21-25}, month = apr, address = {Uz\`es, France}, igmrefpreprint= {hal-00274003}, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/topsa.pdf}, url = {http://hal.archives-ouvertes.fr/view_by_stamp.php?&halsid=7c3i2m2o11b79ossehpeas3fj5&label=JAC2008&langue=fr&action_todo=view&id=hal-00274003&version=1}, keywords = { sand automata, cellular automata, dynamical systems, subshifts}, lang = {EN}, note = { hal-00274003 } } @InProceedings{ IGMA_BliBlaGui06, idhal = {hal-00524049}, pwdhal = {zpl9yej0}, typeupe = {INPROCEEDINGS_international_article}, confdate = {2006}, author = {Blin, Guillaume and Blais, Eric and Guillon, Pierre and Blanchette, Mathieu and El-Mabrouk, Nadia}, labs = {3210,,3210,,}, title = {{{Inferring Gene Orders from Gene Maps using the Breakpoint Distance}}}, booktitle = {4th Annual RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG'06)}, country = {CA}, igmnumconf = {4}, igmnumbisconf = {th}, igmacroconf = {RECOMB-CG}, igmconf = {Annual RECOMB Satellite Workshop on Comparative Genomics}, series = {LNBI}, publisher = {Springer-Verlag}, editor = {Bourque, Guillaume and El-Mabrouk, Nadia}, year = {2006}, volume = {4205}, pages = {99--112}, days = {24-26}, month = sep, address = {Montr\'eal, Quebec}, pdf = {http://igm.univ-mlv.fr/~gblin/pdf/blais_blanchette_blin_guillon_mabrouk_RCG_2006.pdf}, lang = {EN}, note = { } } @PhDThesis{ IGMA_Gui08, author = {Guillon, Pierre}, title = {{Automates cellulaires : dynamiques, simulations, traces}}, type = igm_phddoc, igmtype = {igm_phdDoc}, igmlocal = {true}, school = {Universit\'e Paris-Est}, directeur = {Cervelle, Julien}, encadrant = {Formenti, Enrico}, rapporteur = {Jonoska, Nata\vsa and Margara, Luciano}, examinateur = {B\'eal, Marie-Pierre and Berth\'e, Val\'erie and Mazoyer, Jacques}, abstract = {Un automate cellulaire est un syst\`eme dynamique discret qui mod\'elise des objets ayant une \'evolution parall\`ele synchrone: l'espace est divis\'e en cellules ayant chacune un \'etat et qui \'evoluent toutes selon une m\^eme r\`egle locale, qui ne d\'epend que d'un nombre fini de cellules voisines.\\ Malgr\'e la simplicit\'e de la formalisation de ce syst\`eme, des comportements tr\`es complexes peuvent appara\^itre, qui en font notamment un mod\`ele de calcul. Cette complexit\'e a \'et\'e rattach\'ee \`a diverses th\'eories: topologie, mesure, d\'ecidabilit\'e, information...\\ Nous adoptons ici une approche bas\'ee sur la dynamique symbolique, c'est \`a dire l'\'etude des mots infinis sur un alphabet donn\'e auxquels on applique un d\'ecalage, suppression de la premi\`ere lettre.\\ \`A chaque automate cellulaire peut en effet \^etre associ\'e son trac\'e, l'ensemble des mots infinis repr\'esentant la s\'equence des \'etats successifs pris par la cellule centrale de l'espace - ou un groupe de cellules centrales. On a alors une factorisation topologique: la lecture d'une lettre dans un de ces mots correspond exactement \`a une \'etape de l'\'evolution de l'automate.\\ De nombreuses propri\'et\'es topologiques sont alors transmises par cette factorisation. Inversement, le fait que les cellules \'evoluent toutes de la m\^eme mani\`ere permet de d\'eduire certaines propri\'et\'es de l'automate \`a partir de celles de son trac\'e.\\ La premi\`ere partie de la th\`ese est consacr\'ee \`a ces nombreux liens. Une deuxi\`eme partie pr\'esente des conditions suffisantes pour qu'un ensemble de mots infinis soit le trac\'e d'un automate cellulaire. Enfin, une troisi\`eme partie donne un point de vue plus informatique, en r\'ecapitulant les principaux r\'esultats d'ind\'ecidabilit\'e sur le sujet et en prouvant que toutes les propri\'et\'es du trac\'e qui peuvent se voir infiniment tard sont ind\'ecidables. }, year = {2008}, days = {24}, month = nov, igmnbpages = {152}, pdf = {http://igm.univ-mlv.fr/~pguillon/bib/these.pdf}, keywords = {automates cellulaires, syst\`emes dynamiques, dynamique symbolique, dynamique topologique, sous-d\'ecalages, langages formels, d\'ecidabilit\'e, simulation}, lang = {FR}, note = { Jury : Cervelle, Julien, Formenti, Enrico, Jonoska, Nata\vsa and Margara, Luciano, B\'eal, Marie-Pierre and Berth\'e, Val\'erie and Mazoyer, Jacques (152 pp.) } }