Skip to Main content Skip to Navigation
Conference papers

Angluin Style Finite State Machine Inference with Non-optimal Counterexamples

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Catherine Oriat Connect in order to contact the contributor
Submitted on : Friday, February 28, 2014 - 11:46:30 AM
Last modification on : Sunday, June 26, 2022 - 9:34:53 AM




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, ⟨10.1145/1868044.1868046⟩. ⟨hal-00953394⟩



Record views