Improving Model Inference of Black Box Components having Large Input Test Set


Muhammad Naeem Irfan, Roland Groz, Catherine Oriat ;
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:133-138, 2012.


The deterministic finite automata (DFA) learning algorithm $L*$ has been extended to learn Mealy machine models which are more succinct for \emph{input/output} (i/o) based systems. We propose an optimized learning algorithm $L_1$ to infer Mealy models of software black box components. The $L_1$ algorithm uses a modified observation table and avoids adding unnecessary elements to its columns and rows. The proposed improvements reduce the worst case time complexity. The $L_1$ algorithm is compared with the existing Mealy inference algorithms and the experiments conducted on a comprehensive set confirm the gain.

Related Material