Henry, L; Jéron, T; Markey, N; (2020) Active Learning of Timed Automata with Unobservable Resets. In: International Conference on Formal Modeling and Analysis of Timed Systems FORMATS 2020: Formal Modeling and Analysis of Timed Systems. (pp. pp. 144-160). Springer, Cham

Preview

Text 2007.01637v2.pdf - Accepted Version Download (572kB) | Preview

Abstract

Active learning of timed languages is concerned with the inference of timed automata by observing some of the timed words in their languages. The learner can query for the membership of words in the language, or propose a candidate model and ask if it is equivalent to the target. The major difficulty of this framework is the inference of clock resets, which are 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. 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. This notion is a key to any efficient active-learning procedure for generic timed automata.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item