Learning deterministic probabilistic automata from a model checking perspective

Mao, Hua, Chen, Yingke, Jaeger, Manfred, Nielsen, Thomas D., Larsen, Kim G. and Nielsen, Brian (2016) Learning deterministic probabilistic automata from a model checking perspective. Machine Learning, 105 (2). pp. 255-299. ISSN 0885-6125

Mao et al - Learning deterministic probabilistic automata from a model checking perspective AAM.pdf - Accepted Version

Download (1MB) | Preview
Official URL: http://dx.doi.org/10.1007/s10994-016-5565-9


Probabilistic automata models play an important role in the formal design and analysis of hard- and software systems. In this area of applications, one is often interested in formal model-checking procedures for verifying critical system properties. Since adequate system models are often difficult to design manually, we are interested in learning models from observed system behaviors. To this end we adopt techniques for learning finite probabilistic automata, notably the Alergia algorithm. In this paper we show how to extend the basic algorithm to also learn automata models for both reactive and timed systems. A key question of our investigation is to what extent one can expect a learned model to be a good approximation for the kind of probabilistic properties one wants to verify by model checking. We establish theoretical convergence properties for the learning algorithm as well as for probability estimates of system properties expressed in linear time temporal logic and linear continuous stochastic logic. We empirically compare the learning algorithm with statistical model checking and demonstrate the feasibility of the approach for practical system verification.

Item Type: Article
Uncontrolled Keywords: Probabilistic model checking, Probabilistic automata learning, Linear time temporal logic
Subjects: G400 Computer Science
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Paul Burns
Date Deposited: 13 Jun 2019 15:09
Last Modified: 01 Aug 2021 11:30
URI: http://nrl.northumbria.ac.uk/id/eprint/39681

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics