Learning of Event-Recording Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2010

Learning of Event-Recording Automata

Olga Grinchtein
  • Fonction : Auteur
  • PersonId : 867552
Bengt Jonsson
  • Fonction : Auteur
  • PersonId : 867553
Martin Leucker
  • Fonction : Auteur
  • PersonId : 867554

Résumé

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∗s g, 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 simple DERA, which is similar in spirit to the region graph.
Fichier principal
Vignette du fichier
tcs10-v2.pdf (382.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00459696 , version 1 (24-02-2010)

Identifiants

  • HAL Id : inria-00459696 , version 1

Citer

Olga Grinchtein, Bengt Jonsson, Martin Leucker. Learning of Event-Recording Automata. Theoretical Computer Science, 2010. ⟨inria-00459696⟩

Collections

CONNECT
194 Consultations
496 Téléchargements

Partager

Gmail Facebook X LinkedIn More