Christian Choffrut
LIAFA
Les automates finis traditionnels ont ete des leur debut etendus de facon a pouvoir realiser des fonctions du monoide libre dans lui-meme.
Nous nous interessereons plus particulierement a la sous-classe de fonctions dont l'automate sous-jacent est deterministe (les fonctions sequentielles). Nous rappellerons leur proprietes de decidabiblite, leur caracterisation fonctionnelle en terme de metrique sur le monoide libre, l'existence et le calcul d'un objet "syntaxique" unique qui leur est associe, etc...
Plus generales que les fonctions sequentielles sont les relations entre mots qui sont reconnaissables par un automate fini calculant non pas sur un mot mais sur deux mots (les "automates a deux bandes"). Nous indiquerons comment ces objets travaillent en realite sur des structures max, + et min, +.