"automates finis à oracles"
"automates finis à oracles"
liafa
laboratoire d'informatique algorithmique: fondements et applications
cnrs umr 7089, université paris diderot - paris 7, case 701475205 paris cedex 13 - tél: +33(0)1.44.27.68.45 - fax: +33(0)1.44.27.68.49
annuaire contact accès au liafa ufr d'info liens utiles webmail
accueilactualitésprésentation généralestructure du laboratoireorganigrammeinvitésrapport d'activitéequipes de recherchealgorithmique et combinatoireautomates et applicationsmodélisation et vérificationposters (2004)evénements et séminairespublicationsoutils logicielsoutils scientifiquesautres outilsrelations internationalesinvitésvisite du premier ministre d'ecossethèmes de recherche et projets européensprojets internationauxprojetsthèmes de recherche et projets européensprojets internationauxprojets nationauxavant-projets inriapostes et stages
evénements et séminairesdate: 2005-01-21/2005-01-21 [14h30]auteur: séverine fratani (labri, bordeaux)titre: automates finis à oraclesrésumé: on définit une extension des automates finis (de mots et d'arbres) en joignant à la donnée d'un automate, un vecteur vec(r) de langages qu'on nomme oracle. l'application d'une transition de l'automate à un mot est alors conditionnée par l'appartenance de ce mot au différents langages de l'oracle. on montre que les langages d'arbres reconnus par de tels automates sont exactement les ensembles définissables en msol dans la structure (a*, (succ_a)_{a \in a}, vec(r)). on en déduit des lemmes de transferts permettant de construire des vecteurs vec(r) tels que - (a*, (succ_a)_{a \in a}), vec(r)) admet une msol-décidable - les langages de mots mso-définissables dans (a*, (succ_a)_{a \in a}), vec(r)) (i.e uniques modèles d'une mso-formule) sont exactement les langages reconnu par automate à oracle vec(r'), où vec(r') est mso-définissable dans une structure plus simple.email de l'auteur: fratani [at] labri.fr
© liafa 1995, dernière mise à jour: septembre 2007
webmestre[at]liafa.jussieu.fr
"automates finis à oracles" Précédent 212 Précédent 211 Précédent 210 Précédent 209 Précédent 208 Précédent 207 Précédent 206 Précédent 205 Précédent 204 Précédent 203 Précédent 202 Précédent 201 Précédent 200 Précédent 199 Précédent 198 Précédent 197 Précédent 196 Précédent 195 Précédent 194 Précédent 193 Précédent 192 Précédent 191 Précédent 190 Précédent 189 Précédent 188 Précédent 187 Précédent 186 Précédent 185 Précédent 184 Précédent 183 Suivant 214 Suivant 215 Suivant 216 Suivant 217 Suivant 218 Suivant 219 Suivant 220 Suivant 221 Suivant 222 Suivant 223 Suivant 224 Suivant 225 Suivant 226 Suivant 227 Suivant 228 Suivant 229 Suivant 230 Suivant 231 Suivant 232 Suivant 233 Suivant 234 Suivant 235 Suivant 236 Suivant 237 Suivant 238 Suivant 239 Suivant 240 Suivant 241 Suivant 242 Suivant 243