Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Automates et logiques pour les mots sur un alphabet infini

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

Date
Le mardi 08 janvier 2008 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Alexis Bès (LACL, Université Paris 12 )

Plusieurs modèles d'automates ont été proposés pour manipuler des mots sur un alphabet infini. Ces mots apparaissent par exemple dans l'étude de problèmes de vérification de systèmes distribués ou temporisés, ou encore de manipulation de données semi-structurées. Un objectif commun est d'obtenir un modèle à la fois simple et expressif, et qui conserve tant que possible les bonnes propriétés du modèle classique.

Dans cet exposé on présentera un nouveau type d'automate dans lequel l'alphabet A est vu comme le domaine d'une structure M, et les transitions de l'automate sont des formules du premier ordre écrites dans le langage de M. Ce modèle s'inspire directement de la notion de puissance généralisée de structures introduite par Feferman et Vaught à la fin des années 1950, et généralise un modèle introduit récemment par Choffrut et Grigorieff. On verra qu'il possède de bonnes propriétés de clôture et de décision, ainsi que plusieurs caractérisations logiques. On présentera également une extension du formalisme de Feferman et Vaught qui permet de pallier le manque d'expressivité du modèle initial.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents