Learning of Event-Recording Automata
| Title | Learning of Event-Recording Automata |
| Publication Type | Conference Paper |
| Year of Publication | 2004 |
| Authors | Grinchtein, O, Jonsson, B, Leucker, M |
| Conference Name | Proceedings of the Joint Conferences {FORMATS} and {FTRTFT} |
| Series | Lecture Notes in Computer Science |
| Volume | 3253 |
| 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}
}PDF:
Postscript:
