The efficiency of identifying timed automata and the power of clocks |
| |
Authors: | Sicco Verwer Mathijs de Weerdt |
| |
Affiliation: | a Eindhoven University of Technology, Department of Mathematics and Computer Science (EWI), P.O. 513, 5600 MB, Eindhoven, The Netherlands b Delft University of Technology, Department of Engineering, Mathematics and Computer Science, Mekelweg 4, 2628 CD, Delft, The Netherlands |
| |
Abstract: | We develop theory on the efficiency of identifying (learning) timed automata. In particular, we show that: (i) deterministic timed automata cannot be identified efficiently in the limit from labeled data and (ii) that one-clock deterministic timed automata can be identified efficiently in the limit from labeled data. We prove these results based on the distinguishability of these classes of timed automata. More specifically, we prove that the languages of deterministic timed automata cannot, and that one-clock deterministic timed automata can be distinguished from each other using strings in length bounded by a polynomial. In addition, we provide an algorithm that identifies one-clock deterministic timed automata efficiently from labeled data.Our results have interesting consequences for the power of clocks that are interesting also out of the scope of the identification problem. |
| |
Keywords: | Deterministic timed automata Identification in the limit Complexity |
本文献已被 ScienceDirect 等数据库收录! |
|