The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
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.