Voir la source de Inférence d'automates de Mealy sans ré-initialisation

{{Sujet irl
| labo = LIG
| titre = Inférence d'automates de Mealy sans ré-initialisation 
| equipe = VASCO
| encadrants = Catherine.Oriat@imag.fr
}}

[[Catégorie:IRL]]

=== Thème général === 

Le développement rigoureux de logiciel, basé sur des méthodes formelles, exige
que l'on dispose de modèles du programme. Comme de tels modèles ne sont pas
toujours disponibles, différentes méthodes d'inférence ont été proposées pour
reconstruire ces modèles. 

===  Contexte du travail === 

On suppose que le système peut être représenté, à un
certain niveau d'abstraction, par une machine à états finie ayant certaines
entrées et sorties (automates de Mealy).  L'équipe VASCO du LIG s'intéresse
depuis plusieurs années aux techniques d'inférence "active", qui consistent
construire cette machine à états en observant ses sorties en fonction de
différentes entrées. Ces techniques d'apprentissage reposent sur des tests
en boîte noire, ne supposent pas qu'on dispose du code source, ni même du
code binaire du logiciel.

=== Sujet ===

La plupart des algorithmes d'inférence supposent qu'on peut à tout moment
replacer le système dans son état initial (opération de ré-initialisation).
Cette hypothèse n'est pas satisfaite par tous les systèmes ; parfois cette
opération est possible, mais très coûteuse en temps.

L'objectif de ce travail consiste à formaliser et implémenter un
algorithme combinatoire d'inférence de machine sans ré-initialisation.
Cet algorithme pourra ensuite être comparé à un algorithme
développé par Rivest et Schapire [RV89], qui pourra être
implémenté dans la plateforme d'inférence SIMPA développée
au sein de l'équipe VASCO.

[RS89] Ronald L. Rivest, Robert E. Schapire. Inference of finite automata
using homing sequences. Proceedings of the Twenty-First Annual ACM Symposium
on Theory of Computing, 1989.

=== Résultats attendus ===

* Formalisation d'un algorithme d'inférence combinatoire
* Implantation de cet algorithme et de l'algoritme de Rivest et Schapire dans la plateforme d'inférence SIMPA
* Comparaison expérimentale de la complexité des deux algorithmes

===  Compétences nécessaires === 

Connaissances en théorie des langages : automates