- Renseignements pratiques
- Enseignement
Contact
LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2
Email:
contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37
Le groupe de travail GAMoC
28/01/2015 : [GAMoC] Signals in one-dimensional cellular automata
Tom Besson (LIFO)
Résumé
Lieu : Salle SR3, bâtiment 3IA
27/11/2014 : [GAMoC] On the number of minimal dominating sets on cobipartite, split and interval graphs
Romain Letourneur (LIFO)
Résumé
Débute à 16 h 30. Lieu : SR3, bâtiment 3IA
03/03/2014 : [GAMoC] Automata Network Model of the Naming Game: first results
Javier Vera (Université Adolfo Ibáñez, Santiago, Chili)
Résumé
Débute à 15 h 30. Lieu : Salle SR3, bâtiment 3IA
03/02/2014 : [GAMoC] Distributed algorithms in shared whiteboard models: impact of randomness and links with streaming
Pedro Montealegre (LIFO)
Résumé
Débute à 10 h. Lieu : Salle SR3, bâtiment 3IA
Résumés des groupes de travail
[GAMoC] Signals in one-dimensional cellular automata Tom Besson, LIFO
In this paper, the authors are interested in signals, from the data can be transmitted in a cellular automaton. They study generation of some signals. In this aim, they investigate a notion of constructibility of increasing functions related to the production of words on the initial cell (in the sense of Fisher for the prime numbers). They establish some closure properties on this class of functions. They also exhibit some impossible moves of data.
[GAMoC] On the number of minimal dominating sets on cobipartite, split and interval graphs Romain Letourneur, LIFO
A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159n) minimal dominating sets. Here we establish upper bounds on this maximum number of minimal dominating sets for cobipartite and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For interval graphs, we show that the number of minimal dominating sets is at most 3n/3~1.4423n, which is the best possible bound. For cobipartite graphs, we lower the O(1.5875n) upper bound from Couturier to O(1.4511n). In the talk we also discuss an upper bound on the maximum number of minimal dominating sets for split graphs.
This is a joint work with J.-F. Couturier and M. Liedloff.
[GAMoC] Automata Network Model of the Naming Game: first results Javier Vera, Université Adolfo Ibáñez, Santiago, Chili
The Naming Game is a model to solve the problem of developing a shared communication system in a community of speakers. This game is played by a finite population of agents, observing the same unique object and trying to communicate its name to one another.
We study an automata network approach to Naming Game by defining local rules. The study of the dynamics is based on the definition of a bounded and monotonic energy functional. In particular, we found transient lengths for two kinds of updating schemes. Along with the above, I will show some computer simulations of the dynamics.
[GAMoC] Distributed algorithms in shared whiteboard models: impact of randomness and links with streaming Pedro Montealegre, LIFO
Consider the following distributed computing model: there is a labeled graph where each node, knowing just its own label and the label of its neighbors, is allowed to send a message to some central entity, called the referee. We ask for what kind of structural properties of the graph can be decided by the referee, using just one message from each node, and when the size of a message is limited to be sublinear in the size of the graph.
In this talk I will give a track on the main topics that I have studied during my (almost) first year of thesis work: Main open problems; other related models, specially streaming; the impact of randomness in the previous results, and some incipient results.
Université d'Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 