Groupe de Travail "Graphes et Logique"
Responsable : Olivier Ly
Mardi 11h00 - salle 076 (rez-de-chaussée du LaBRI) -
Université Bordeaux 1
Exposés à venir :- 28 novembre 2006 -
Pascal Weil
(LaBRI)
Le problème de minimisation de Whitehead
Soit F un groupe libre de rang fini et soit A une base de F. Les
éléments de F peuvent être représentés par des mots réduits écrits sur
l'alphabet A \cup A^{-1}. Le problème de minimisation de Whitehead
est le suivant : étant donné un élément u de F, trouver un mot de
longueur minimale parmi les images de u par un automorphisme de F.
Les sous-groupes de rang fini de F peuvent être représentés, quant àÂ
eux, par des automates finis particuliers sur l'alphabet A \cup
A^{-1}, et on peut considérer le nombre des états de ces automates
comme une mesure de la taille des sous-groupes. Le problème de
minimisation s'étend alors aux sous-groupes : étant donné un
sous-groupe de rang fini H, trouver un sous-groupe de taille minimale
parmi les images de H par un automorphisme de F.
Je présenterai un algorithme classique de résolution de ces problèmes,
qui est polynomial en la longueur du mot u (resp. en la taille du
sous- groupe H) et exponentiel en la cardinalité de A. J'expliquerai
ensuite comment transformer cet algorithme pour trouver une solution
en temps polynomial en toutes les données. Les ingrédients font
appararaître de façon inattendue la recherche de coupes minimales dans
un graphe, et même dans un hypergraphe.
- 5 décembre 2006 -
Hugo Gimbert
(LIX École polytechnique et LIAFA, Paris 7)
Stochastic games with pure stationary optimal strategies
Part of this work is joint work with Wieslaw Zielonka.
We study two-players zero-sum stochastic games with perfect information.
Such games are natural models for controllable discrete event systems
with stochastic behaviour.
In those games, the payoffs of players can be computed in various ways.
This defines different classes of games, such as parity games,
discounted games, mean-payoff games or limsup games.
Those games share a common non-trivial property :
both players have optimal strategies which are pure (non-randomized) and
stationary (independent of the history of the play).
Recently, existence of such optimal strategies in non-stochastic games
has attracted a lot of attention.
Indeed, this property is the key to obtain complementation results in
automata theory,
and decidability result for verification of infinite state systems.
In this talk, we are interested in stochastic games with finitely many
states.
We define the class of "submixing" games, and prove that such a game
admits pure stationary optimal strategies.
This result has several corollaries.
First, it unifies various disparate proofs of existence of pure
stationary optimal strategies in limsup, parity and mean-payoff games.
Second, we generate new examples of games with pure stationary optimal
strategies.
Thus, we obtain new classes of decidable controller synthesis problems.
- décembre 2006 -
Olivier Ly
(LaBRI)
A propos d'une équation de langage
Exposés Passés :- 14/11/06 -
Bruno Courcelle
(LaBRI)
Etiquettage de distance en présence de zones interdites
Soit un graphe à n sommets décomposé comme il faut.
On veut associer à chaque sommet x une étiquette
I(x) telle que si l'on connait les I(y) pour tous les y dans un ensemble X on peut
alors déterminer pour tous u et v dans X la longueur d'un plus court chemin de u à v
- qui évite un sous-ensemble Y de X de sommets interdits,
- qui n'emprunte pas un ensemble B d'arêtes brisées (dont les extrémités sont dans X).
Changer X,Y et B ne nécessite pas de recalculer la décomposition et l'étiquettage.
On veut aussi déterminer un chemin optimal sous ces contraintes.
Résultat : Pour un graphe de largeur de largeur arborescente ou de "largeur de clique à étiquettes multiples" au plus k,
on peut faire cela avec des étiquettes de longueur O(k ^2 . (log(n))^2)
Cette construction introduit une variante de la largeur de clique
qui permet un équilibrage des termes avec perte d'optimalité linéaire.
Elle est garantie sans LSOM, une fois n'est pas coutume, car elle refait
sans recours à la logique une construction de Vanicat et l'orateur.
- 24/10/06 -
Manfred Kufleitner
(LaBRI - Stuttgart)
Trace languages and the variety DA
Traces have been introduced by Mazurkiewicz in 1977 as a
generalization of words to describe the behavior of concurrent
processes. A lot of characterizations for the class of recognizable
trace languages and for the the class of star-free trace languages are
known. These include for example algebraic properties, specialized
automata models and logical fragments. For more restricted classes of
recognizable trace languages very little research has been done.
A result from the early 90s is that a trace-language is star-free if
and only if its syntactic monoid is aperiodic. An important subclass
of aperiodic monoids is the variety DA. Over words, many
characterizations have been found for languages whose syntactic monoid
is in DA. We show which of them also hold for traces and which of them
do not hold. For logical fragments, a crucial property is whether one
can express concurrency or not.
- 17/10/06 -
Alexei Miasnikov
(Montreal, McGill University)
Zero-one laws and random subgraphs of Cayley graphs
I am going to discuss asymptoic properties of finite subgraphs of a
fixed Cayley graph $\Gamma$. It turns out that the classical Zero-One
law also holds in this situation, i.e., for any first-orfer sentence
either this sentence or its negation holds with probability one on
finite subgraphs of $\Gamma$. I am going to touch on some relations
between these results and the axioms of the universal theories of a
given group.
One of the key ingredients of our approach is to show that the random
subgraphs of $\Gamma$ (those that have a non-zero probability to
occur) are all elementarily equivalent to each other. This brings
some interesting connections with percolation theory on graphs. At
the end of the talk I will discribe a much wider class of graphs where
our results still hold.
The talk is intended to be elementary and self-contained.
(joint With R. Gilman and Yu. Gurevich)
- 10/10/06 -
Dietrich Kuske
(Leipzig)
Compatibility of Stupp's and Muchnik's iteration with fragments of monadic second order logic
We investigate the relation between the theory of the iterations in
the sense of Shelah-Stupp and of Muchnik, resp., and the theory of
the base structure for several logics. These logics are obtained
from the restriction of set quantification in monadic second order
logic to certain subsets like, e.g., finite sets, chains, and finite
unions of chains. We show that these theories of the Shelah-Stupp
iteration can be reduced to corresponding theories of the base
structure. This fails for Muchnik's iteration.