Le probl me de l' quivalence pour les automates de B chi fortement non ambig s

Niveau: Supérieur, Master, Bac+4
Problème de l'équivalence pour les automates non-ambigus Nicolas BOUSQUET sous la tutelle de Christof LÖDING, Wolfgang THOMAS Juin-Aout 2009 Résumé Ceci est le rapport du travail que j'ai e?ectué durant l'été 2009 sous la tutelle de Christof Löding et Wolfgang Thomas. Il a porté sur l'étude du problème de l'équivalence pour les automates de Büchi non-ambigus. Ce rapport est rédigé en francais et les annexes sont les preuves en anglais des deux résultats principaux de mon stage : décision du problème de l'équivalence pour les automates de Büchi fortement non-ambigus et pour les automates fortement k-ambigus en temps polynomial. 1

• problème de l'équivalence


• automate


• automates déterministes


• classe des problèmes de décision décidable en temps poly


• fossé de classe de complexité entre les problèmes


• ple classique illustrant le fossé de taille entre automates déterministes


• classe d'automates