A Theory of History Dependent Abstractions for Learning Interface Automata?

Abstract. History dependent abstraction operators are the key for scal-ing existing methods for active learning of automata to realistic appli-cations. Recently, Aarts, Jonsson & Uijen have proposed a framework for history dependent abstraction operators. Using this framework they succeeded to automatically infer models of several realistic software com-ponents with large state spaces, including fragments of the TCP and SIP protocols. Despite this success, the approach of Aarts et al. suffers from limitations that seriously hinder its applicability in practice. In this article, we get rid of some of these limitations and present four impor-tant generalizations/improvements of the theory of history dependent abstraction operators. Our abstraction framework supports: (a) inter-face automata instead of the more restricted Mealy machines, (b) the concept of a learning purpose, which allows one to restrict the learn-ing process to relevant behaviors only, (c) a richer class of abstractions, which includes abstractions that overapproximate the behavior of the system-under-test, and (d) a conceptually superior approach for testing correctness of the hypotheses that are generated by the learner.