Skip to Main content Skip to Navigation
Conference papers

Active learning of timed automata with unobservable resets

Léo Henry 1 Thierry Jéron 1 Nicolas Markey 1
1 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Active learning of timed languages is concerned with the inference of timed automata from observed timed words. The agent can query for the membership of words in the target language, or propose a candidate model and verify its equivalence to the target. The major difficulty of this framework is the inference of clock resets, central to the dynamics of timed automata, but not directly observable. Interesting first steps have already been made by restricting to the subclass of event-recording automata, where clock resets are tied to observations. In order to advance towards learning of general timed automata, we generalize this method to a new class, called reset-free event-recording automata, where some transitions may reset no clocks. This offers the same challenges as generic timed automata while keeping the simpler framework of event-recording automata for the sake of readability. Central to our contribution is the notion of invalidity, and the algorithm and data structures to deal with it, allowing on-the-fly detection and pruning of reset hypotheses that contradict observations, a key to any efficient active-learning procedure for generic timed automata.
Complete list of metadata

https://hal.inria.fr/hal-02896517
Contributor : Léo Henry <>
Submitted on : Friday, July 10, 2020 - 3:44:16 PM
Last modification on : Tuesday, February 9, 2021 - 3:29:13 AM

Links full text

Identifiers

  • HAL Id : hal-02896517, version 1
  • ARXIV : 2007.01637

Citation

Léo Henry, Thierry Jéron, Nicolas Markey. Active learning of timed automata with unobservable resets. FORMATS 2020 - 18th International Conference on Formal Modeling and Analysis of Timed Systems, Sep 2020, Vienna, Austria. pp.1-26. ⟨hal-02896517⟩

Share

Metrics

Record views

53