Angluin Style Finite State Machine Inference with Non-optimal Counterexamples

Muhammad Naeem Irfan 1 Catherine Oriat 1 Roland Groz 1
1 VASCO
LIG - Laboratoire d'Informatique de Grenoble
Abstract : Angluin's algorithm is a well known approach for learning black boxes as minimal deterministic finite automata in polynomial time. In order to infer finite state machines instead of automata, different variants of this algorithm have been proposed. These algorithms rely on two types of queries which can be asked to an oracle: output and equivalence queries. If the black box is not equivalent to the learnt model, the oracle replies with a counterexample. The complexity of these algorithms depends on the length of the counterexamples provided by the oracle. The aim of this paper is to compare the average practical complexity of three of these algorithms in the case of poor oracles, in particular when the counterexamples are constructed with random walks.
Type de document :
Communication dans un congrès
1st International Workshop on Model Inference In Testing, MIIT 2010, 2010, Trento, pp.11-19, 2010, 〈10.1145/1868044.1868046〉
Liste complète des métadonnées

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

Identifiants

Collections

Citation

Muhammad Naeem Irfan, Catherine Oriat, Roland Groz. Angluin Style Finite State Machine Inference with Non-optimal Counterexamples. 1st International Workshop on Model Inference In Testing, MIIT 2010, 2010, Trento, pp.11-19, 2010, 〈10.1145/1868044.1868046〉. 〈hal-00953394〉

Partager

Métriques

Consultations de la notice

124