The efficiency of identifying timed automata and the power of clocks

S.E. Verwer, M. Weerdt, de, C. Witteveen

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)606-625
JournalInformation and Computation
Volume209
Issue number3
DOIs
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'The efficiency of identifying timed automata and the power of clocks'. Together they form a unique fingerprint.

  • Cite this