Characterization of Lattices Induced by (extended) Chip Firing Games

Clémence Magnien 1 Ha Duong Phan 1 Laurent Vuillon 1
1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
Abstract : The Chip Firing Game (CFG) is a discrete dynamical model used in physics, computer science and economics. It is known that the set of configurationsreachable from an initial configuration (this set is called the \textitconfiguration space) can be ordered as a lattice. We first present a structural result about this model, which allows us to introduce some useful tools for describing those lattices. Then we establish that the class of lattices that are the configuration space of a CFG is strictly between the class of distributive lattices and the class of upper locally distributive (or ULD) lattices. Finally we propose an extension of the model, the \textitcoloured Chip Firing Game, which generates exactly the class of ULD lattices.
Keywords : Sand Pile Model Discrete Dynamical Model Lattice Chip Firing Game
Type de document :
Communication dans un congrès
Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.229-244, 2001, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01182957
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 6 août 2015 - 08:53:48
Dernière modification le : jeudi 11 janvier 2018 - 06:17:41
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:43:07

Fichier

dmAA0117.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01182957, version 1

Collections

INSMI | USPC | TDS-MACS

Citation

Clémence Magnien, Ha Duong Phan, Laurent Vuillon. Characterization of Lattices Induced by (extended) Chip Firing Games. Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.229-244, 2001, DMTCS Proceedings. 〈hal-01182957〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

175

Téléchargements de fichiers

118

Contact


archive-ouverte@inria.fr