DLIQ: A Deterministic Finite Automaton Learning Algorithm through Inverse Queries

Abstract

Automaton learning has attained a renewed interest in many interesting areas of software engineering including formal verification, software testing and model inference. An automaton learning algorithm typically learns the regular language of a DFA with the help of queries. These queries are posed by the learner (Learning Algorithm) to a Minimally Adequate Teacher (MAT). The MAT can generally answer two types of queries asked by the learning algorithm; membership queries and equivalence queries. Learning algorithms can be categorized into two broad categories: incremental and complete learning algorithms. Likewise, these can be designed for 1-bit learning or k-bit learning. Existing automaton learning algorithms have polynomial (atleast cubic) time complexity in the presence of a MAT. Therefore, sometimes these algorithms even become fail to learn large complex software systems. In this research work, we have reduced the complexity of the Deterministic Finite Automaton (DFA) learning into lower bounds (from cubic to square form). For this, we introduce an efficient complete DFA learning algorithm through Inverse Queries (DLIQ) based on the concept of inverse queries introduced by John Hopcroft for state minimization of a DFA. The DLIQ algorithm takes O(|Ps||F|+|Σ|N) complexity in the presence of a MAT which is also equipped to answer inverse queries. We give a theoretical analysis of the proposed algorithm along with providing a proof correctness and termination of the DLIQ algorithm. We also compare the performance of DLIQ with ID algorithm by implementing an evaluation framework. Our results depict that DLIQ is more efficient than ID algorithm in terms of time complexity.