Automata Learning with Automated Alphabet Abstraction Refinement

Falk Howar, Bernhard Steffen, Maik Merten: Automata Learning with Automated Alphabet Abstraction Refinement. In: VMCAI 2011, LNCS 6538, pp. 263-277. Springer, 2011


Abstraction is the key when learning behavioral models of realistic systems, but also the cause of a major problem: the introduction of non-determinism. In this paper, we introduce a method for refining a given abstraction to automatically regain a deterministic behavior on-the-fly during the learning process. Thus the control over abstraction becomes part of the learning process, with the effect that detected non-determinism does not lead to failure, but to a dynamic alphabet abstraction refinement. Like automata learning itself, this method in general is neither sound nor complete, but it also enjoys similar convergence properties even for infinite systems as long as the concrete system itself behaves deterministically, as illustrated along a concrete example.

Download PDF
Comments are closed for this post.