Miaomiao Zhang, Professor, School of Software, Tongji University

Zhongzhi Bai, Professor

PAC Learning of Deterministic One-Clock Timed Automata

10:00-11:00 October 22(Saturday), Tencent Meeting ID: 212-980-950

We study the problem of learning deterministic one-clock timed automata in the framework of PAC (probably approximately correct) learning. The use of PAC learning relaxes the assumption of having a teacher that can answer equivalence queries exactly, replacing it with approximate answers from testing on a set of samples. The framework provides correctness guarantees in terms of error and confidence parameters. We further discuss several improvements to the basic PAC algorithm. This includes a special sampling method, and the use of comparator and counterexample minimization to reduce the number of equivalence queries. We implemented a prototype for our learning algorithm, and conducted experiments on learning the TCP protocol as well as a number of randomly generated automata. The results demonstrate the effectiveness of our approach, as well as the importance of the various improvements for learning complex models.