Learning of Event-Recording Automata

TitleLearning of Event-Recording Automata
Publication TypeConference Paper
Year of Publication2004
AuthorsGrinchtein, O, Jonsson, B, Leucker, M
Conference NameProceedings of the Joint Conferences {FORMATS} and {FTRTFT}
SeriesLecture Notes in Computer Science
Volume3253
Abstract

We extend Angluin's algorithm for on-line learning of regular languages to the setting of timed systems. We consider systems that can be described by a class of deterministic event-recording automata. Our algorithm learns a description by asking a sequence of membership queries (does the system accept a given timed word?) and equivalence queries (is a hypothesized description equivalent to the correct one?). In the constructed description, states are identified by sequences of symbols; timing constraints on transitions are learned by adapting algorithms for learning hypercubes. The number of membership queries is polynomially in the minimal zone graph and in the biggest constant of the automaton to learn.

Bibtex: 
@inproceedings {GrinchteinJL04,
	title = {Learning of Event-Recording Automata},
	booktitle = {Proceedings of the Joint Conferences {FORMATS} and {FTRTFT}},
	series = {Lecture Notes in Computer Science},
	volume = {3253},
	year = {2004},
	abstract = {We extend Angluin{\textquoteright}s algorithm for on-line learning of regular languages to the setting of timed systems. We consider systems that can be described by a class of deterministic event-recording automata. Our algorithm learns a description by asking a sequence of membership queries (does the system accept a given timed word?) and equivalence queries (is a hypothesized description equivalent to the correct one?). In the constructed description, states are identified by sequences of symbols; timing constraints on transitions are learned by adapting algorithms for learning hypercubes. The number of membership queries is polynomially in the minimal zone graph and in the biggest constant of the automaton to learn.},
	author = {Olga Grinchtein and Bengt Jonsson and Martin Leucker}
}
Postscript: