Learning of timed systems

Speaker: Olga Grinchtein

Abstract:

We present an algorithm for constructing a timed-automaton model of a system from information obtained by observing its external behavior. The construction of models from observations of system behavior can be seen as a learning problem. For finite-state reactive systems, it means to construct a (deterministic) finite automaton from the answers to a finite set of membership queries, each of which asks whether a certain word is accepted by the automaton or not. This problem is well understood, e.g., by the work by Angluin. We extend this approach to learning of timed systems, modeled by deterministic event-recording automata. Our construction deviates from previous work and that of Angluin in that it first constructs a so called timed decision tree from observations of system behavior. When sufficiently many observations have been recorded, this decision tree is folded into an event-recording automaton.