@TechReport{	  it:2008-013,
  author	= {Olga Grinchtein and Bengt Jonsson and Martin Leucker},
  title		= {Learning of Event-Recording Automata},
  institution	= {Department of Information Technology, Uppsala University},
  department	= {Division of Computer Systems},
  year		= {2008},
  number	= {2008-013},
  month		= apr,
  abstract	= {In regular inference, a regular language is inferred from
		  answers to a finite set of membership queries, each of
		  which asks whether the language contains a certain word.
		  One of the most well-known regular inference algorithms is
		  the $L^*$ algorithm due to Dana Angluin. However, there are
		  almost no extensions of these algorithms to the setting of
		  timed systems. We extend Angluin's algorithm for on-line
		  learning of regular languages to the setting of timed
		  systems. Since timed automata can freely use an arbitrary
		  number of clocks, we restrict our attention to systems that
		  can be described by deterministic event-recording automata
		  (DERAs). We present three algorithms, $TL_sg^*$, $TL_nsg^*$
		  and $TL_s^*$, for inference of DERAs. In $TL_sg^*$ and
		  $TL_nsg^*$, we further restrict event-recording automata to
		  be event-deterministic in the sense that each state has at
		  most one outgoing transition per action; learning such an
		  automaton becomes significantly more tractable. The
		  algorithm $TL_nsg^*$ builds on $TL_sg^*$, by attempts to
		  construct a smaller (in number of locations) automaton.
		  Finally, $TL_s^*$ is a learning algorithm for a full class
		  of deterministic event-recording automata, which infers a
		  so called \emph{simple} DERA, which is similar in spirit to
		  the region graph.}
}