Combining Exact and Metaheuristic Techniques for Learning Extended Finite-State Machines from Test Scenarios and Temporal Properties

This paper addresses the problem of learning extended finite-state machines (EFSMs) from user-specified behavior examples (test scenarios) and temporal properties. We show how to combine exact EFSM inference algorithms (that always find a solution if it exists) and metaheuristics to derive an efficient combined EFSM learning algorithm. We also present a new exact EFSM inference algorithm based on Constraint Satisfaction Problem (CSP) solvers. Experimental results are reported showing that the new combined algorithm significantly outperforms a previously used metaheuristic.