Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00953397
Contributor : Catherine Oriat <>
Submitted on : Friday, February 28, 2014 - 11:46:36 AM
Last modification on : Tuesday, December 8, 2020 - 10:18:09 AM

Identifiers

  • 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. ⟨hal-00953397⟩

Share

Metrics

Record views

110