La journée se tiendra en salle SR1, au premier étage du LIFO.

Programme

Les créneaux restant souples.

Exposés

Jérôme Durand-Lose, L'irrationalité permet de calculer avec une machine à signaux à trois vitesses

Résumé : Après une brève présentation des machines à signaux, nous montrons que calculer est possible avec 4 vitesses mais impossible avec deux. Nous nous concentrons alors sur le cas de 3 vitesses. Si la machine et la configuration sont définies avec des nombres rationnels (à renormalisation près) alors le calcul est prisonnier d'un grillage rendant tout calcul impossible. En revanche, la présence d'une position irrationnelle permet de simuler une machine de Turing.

Dieter Kratsch (Université de Lorraine, Metz), Cliques and Clubs

Résumé : Clubs are generalizations of cliques. For a positive integer $s$, an $s$-club in a graph $G$ is a set of vertices that induces a subgraph of $G$ of diameter at most $s$. The importance and fame of cliques are evident, whereas clubs have been proposed and studied as a more realistic models for practical applications. We present new results on several graph classes.
To this purpose we study a relation of clubs and cliques.
For a positive integer $s$, we say that a graph class $\mathcal{G}$ has the $s$-clique-power property if for every graph $G\in\mathcal{G}$, every maximal clique in $G^s$ is an $s$-club in $G$. Our main combinatorial results show that both 4-chordal graphs and AT-free graphs have the $s$-clique-power property for all $s\ge 2$. This has various algorithmic consequences.
In particular we show that a maximum $s$-club in $G$ can be computed in polynomial time when $G$ is a chordal bipartite or a strongly chordal or a distance hereditary graph. On weakly chordal graphs, we obtain a polynomial-time algorithm when $s$ is an odd integer, which is best possible as the problem is NP-hard for even values of $s$. We complement these results by proving the NP-hardness of the problem for every fixed $s$ on 4-chordal graphs. Finally, if $G$ is an AT-free graph, we prove that the problem can be solved in polynomial time when $s\ge2$, which gives an interesting contrast to the fact that the problem is NP-hard for $s=1$ on this graph class.

Nicolas Ollinger, A smart machine
Joint work with J. Cassaigne, R. Torres and A. Gajardo.

Résumé : In this talk, I will present a Small Minimal Aperiodic Reversible Turing machine designed by J. Cassaigne with analysis and proofs of its properties by R. Torres. I will then explain how such a machine can be used to solve some conjectures from a previous work with J. Kari, proving undecidability results concerning dynamical properties of Turing machines connected to mortality questions introduced by P.K. Hooper.

Ioan Todinca, Treewidth parameterized by the vertex cover number
Joint work with M. Chapelle, M. Liedloff and Y. Villanger.

Résumé : Given a graph G, a vertex cover is a set C of vertices such that G-C contains no edge. The vertex cover number of G is the minimum size of a vertex cover.
We give here an algorithm computing the treewidth in time O(4^k poly(n)), where k is the vertex cover number of the input graph. If time, we will briefly discuss how to improve this algorithm to run in O(3^k poly(n)) time.

Retour aux évènements 2013