Learning One-Clock Timed Automata
Lecture notes in computer science, pp. 444–462
Abstract
We present an algorithm for active learning of deterministic timed automata with a single clock. The algorithm is within the framework of Angluin’s $$L^*$$ algorithm and inspired by existing work on the active learning of symbolic automata. Due to the need of guessing for each transition whether it resets the clock, the algorithm is of exponential complexity in the size of the learned automata. Before presenting this algorithm, we propose a simpler version where the teacher is assumed to be smart in the sense of being able to provide the reset information. We show that this simpler setting yields a polynomial complexity of the learning process. Both of the algorithms are implemented and evaluated on a collection of randomly generated examples. We furthermore demonstrate the simpler algorithm on the functional specification of the TCP protocol.
Authors 5
-
Jie An corresponding
Affiliation as printed
School of Software Engineering, Tongji University, Shanghai, China
-
Chinese Academy of Sciences · Institute of Software · University of Chinese Academy of Sciences · State Key Laboratory of Computer Science · RWTH Aachen University
Affiliation as printed
Lehrstuhl für Informatik 2, RWTH Aachen University, Aachen, Germany
State Key Lab. of Computer Science, Institute of Software, CAS, Beijing, China
University of Chinese Academy of Sciences, Beijing, China
-
Chinese Academy of Sciences · Institute of Software · University of Chinese Academy of Sciences · State Key Laboratory of Computer Science
Affiliation as printed
State Key Lab. of Computer Science, Institute of Software, CAS, Beijing, China
University of Chinese Academy of Sciences, Beijing, China
-
Naijun Zhan corresponding
Chinese Academy of Sciences · Institute of Software · University of Chinese Academy of Sciences · State Key Laboratory of Computer Science
Affiliation as printed
State Key Lab. of Computer Science, Institute of Software, CAS, Beijing, China
University of Chinese Academy of Sciences, Beijing, China
-
Miaomiao Zhang corresponding
Affiliation as printed
School of Software Engineering, Tongji University, Shanghai, China
Cited by 33 stored of 33
No patents citing this paper on Lens.org (checked 2026-10-06).