Print Email Facebook Twitter The efficiency of identifying timed automata and the power of clocks Title The efficiency of identifying timed automata and the power of clocks Author Verwer, S. De Weerdt, M.M. Witteveen, C. Faculty Electrical Engineering, Mathematics and Computer Science Date 2010-11-18 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. Subject deterministic timed automataidentification in the limitcomplexity To reference this document use: http://resolver.tudelft.nl/uuid:1b229891-aed4-4def-b022-c4dab1b94b08 DOI https://doi.org/10.1016/j.ic.2010.11.023 Publisher Elsevier ISSN 0890-5401 Source Information and Computation, 209 (3), 2011 Part of collection Institutional Repository Document type journal article Rights © 2010 Elsevier Files PDF Verwer_2011.pdf 514.49 KB Close viewer /islandora/object/uuid:1b229891-aed4-4def-b022-c4dab1b94b08/datastream/OBJ/view