@TechReport{ it:2008-014,
author = {Olga Grinchtein and Bengt Jonsson},
title = {Inference of Event-Recording Automata using Timed Decision
Trees},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Computer Systems},
year = {2008},
number = {2008-014},
month = apr,
abstract = {In \emph{regular inference}, the problem is to infer a
regular language, typically represented by a deterministic
finite automaton (DFA) from answers to a finite set of
membership queries, each of which asks whether the language
contains a certain word. There are many algorithms for
learning DFAs, the most well-known being the $L^*$
algorithm due to Dana Angluin. However, there are almost no
extensions of these algorithms to the setting of timed
systems. We present an algorithm for inferring a model of a
timed system using Angluin's setup. One of the most popular
model for timed system is timed automata. Since timed
automata can freely use an arbitrary number of clocks, we
restrict our attention to systems that can be described by
\emph{event-recording automata} (DERAs). In previous work,
we have presented an algorithm for inferring a DERA in the
form of a region graph. In this paper, we present a novel
inference algorithm for DERAs, which avoids constructing a
(usually prohibitively large) region graph. We must then
develop techniques for inferring guards on transitions of a
DERA. Our construction deviates from previous work on
inference of DERAs in that it first constructs a so called
timed decision tree from observations of system behavior,
which is thereafter folded into an automaton.}
}