The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning

Malte Isberner, Falk Howar, Bernhard Steffen: The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning. In RV 2014, LNCS 8734, pp. 307-322. Springer, 2014

Abstract

In this paper we present TTT, a novel active automata learning algorithm formulated in the Minimally Adequate Teacher (MAT) framework. The distinguishing characteristic of TTT is its redundancy-free organization of observations, which can be exploited to achieve optimal (linear) space complexity. This is thanks to a thorough analysis of counterexamples, extracting and storing only the essential refining information. TTT is therefore particularly well-suited for application in a runtime verification context, where counterexamples (obtained, e.g., via monitoring) may be excessively long: as the execution time of a test sequence typically grows with its length, this would otherwise cause severe performance degradation. We illustrate the impact of TTT’s consequent redundancy-free approach along a number of examples.

Download PDF
Comments are closed for this post.