Efficiently learning timed system models from observations

Efficiently learning timed system models from observations

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

Electrical Engineering, Mathematics and Computer Science

Software Computer Technology

2008-05-19

This paper describes an efficient algorithm for learning a timed model from observations. The algorithm is based on the state merging method for learning a deterministic finite state automaton (DFA). This method and its problem have been the subject of many studies within the grammatical inference field, see e.g. (de la Higuera, 2005). Consequently, it enjoys a sound theoretical basis which can be used to prove properties of our algorithm. For example, while it has long been known that learning DFAs is NP-complete, it has been shown that DFAs can be learned in the limit from polynomial time and data (efficiently in the limit) using a state merging method.

http://resolver.tudelft.nl/uuid:f0e05366-b676-4393-9419-0739a594064c

Benelearn 2008: Proceedings of the Annual Machine Learning Conference of Belgium and the Netherlands, Spa, Belgium, 19-20 May 2008

Institutional Repository

conference paper

(c) 2008 The Author(s)