Séminaire du 12 décembre 2014

Lieu

LACL (Créteil) en salle 223, au 2e étage du bâtiment I- comment y aller

Programme

14h00-15h00: Stefan Goeller, CSNR-LSV, "Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete",

Abstract: The reachability problem for vector addition systems with states (VASS) is shown PSPACE-complete when the dimension is two. This improves on a previously known doubly-exponential time bound established by Howell, Rosier, Huynh and Yen in 1986. The coverability and boundedness problems are also noted to be PSPACE-complete. Some complexity results are also given for the reachability problem in two-dimensional VASS and in integer VASS when numbers are encoded in unary.

15h00-15h30 : Adrien Basso-Blandin, Ibisc, "Gubs, un langage de description comportementale pour la biologie de synthèse".

Abstract: La biologie de synthèse est un domaine émergent en quête d’outils afin de formaliser et d’automatiser la caractérisation et la conception de systèmes biologiques. Dans ce cadre, nous proposons de définir le langage GUBS (Genetic Unified Behaviour Specification) utilisé pour spécifier de manière comportementale les systèmes biologiques à synthétiser. De cette définition, le compilateur Ggc recherche un assemblage de composants biologiques capable de reproduire le comportement spécifié.

Gubs est un langage déclaratif que nous pouvons assimiler à un langage de requêtes évolué de recherche de comportements décrits par un ensemble de relations causales. Associé à ce langage, le compilateur Ggc sélectionne automatiquement les composants pour qu’une fois assemblés leur comportement collectif "inclut" celui décrit. La compilation d’une spécification Gubs s’appuie sur le principe d’ACI-Unification en utilisant plus généralement un schéma similaire au système de preuve automatique qui permet de garantir formellement la correction de cet assemblage.

15h30-16h00: pause café

16h00-16h30: vie du groupe