Skip to Main content Skip to Navigation
Conference papers

Characterization of Lattices Induced by (extended) Chip Firing Games

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01182957
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 6, 2015 - 8:53:48 AM
Last modification on : Thursday, June 3, 2021 - 4:18:10 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:43:07 AM

File

dmAA0117.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01182957, version 1

Collections

Citation

Clémence Magnien, Ha Duong Phan, Laurent Vuillon. Characterization of Lattices Induced by (extended) Chip Firing Games. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. pp.229-244. ⟨hal-01182957⟩

Share

Metrics

Record views

319

Files downloads

650