Optimising Angluin Algorithm L* by Minimising the Number of Membership Queries to Process Counterexamples

Muhammad Naeem Irfan 1 Roland Groz 1 Catherine Oriat 1
1 VASCO
LIG - Laboratoire d'Informatique de Grenoble
Abstract : Angluin algorithm L* is a well known approach for learning unknown models as minimal deterministic finite automata (DFA) in polynomial time. It uses concept of oracle which presumably knows the target model and comes up with a counterexample, if the conjectured model is not correct. This algorithm can be used to infer the models of software artefacts and a cheap oracle for such components uses random strings (built from inputs) to verify the inferred models. In such cases and others the provided counterexamples are rarely minimal. The length of the counterexample is an important parameter to the complexity of the algorithm. The proposed technique tends to reduce the impact of non minimal counterexamples. The gain of the proposed algorithm is confirmed by considering a set of experiments on DFA learning.
Type de document :
Communication dans un congrès
Zulu Workshop, 2010, Valencia, 2010
Liste complète des métadonnées

https://hal.inria.fr/hal-00953397
Contributeur : Catherine Oriat <>
Soumis le : vendredi 28 février 2014 - 11:46:36
Dernière modification le : jeudi 11 janvier 2018 - 06:26:40

Identifiants

  • HAL Id : hal-00953397, version 1

Collections

Citation

Muhammad Naeem Irfan, Roland Groz, Catherine Oriat. Optimising Angluin Algorithm L* by Minimising the Number of Membership Queries to Process Counterexamples. Zulu Workshop, 2010, Valencia, 2010. 〈hal-00953397〉

Partager

Métriques

Consultations de la notice

70