Learning Markov models for stationary system behaviors

Yingke Chen*, Hua Mao, Manfred Jaeger, Thomas Dyhre Nielsen, Kim Guldstrand Larsen, Brian Nielsen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Citations (Scopus)


Establishing an accurate model for formal verification of an existing hardware or software system is often a manual process that is both time consuming and resource demanding. In order to ease the model construction phase, methods have recently been proposed for automatically learning accurate system models from data in the form of observations of the target system. Common for these approaches is that they assume the data to consist of multiple independent observation sequences. However, for certain types of systems, in particular many running embedded systems, one would only have access to a single long observation sequence, and in these situations existing automatic learning methods cannot be applied. In this paper, we adapt algorithms for learning variable order Markov chains from a single observation sequence of a target system, so that stationary system properties can be verified using the learned model. Experiments demonstrate that system properties (formulated as stationary probabilities of LTL formulas) can be reliably identified using the learned model.

Original languageEnglish
Title of host publicationNASA Formal Methods
Subtitle of host publication4th International Symposium, NFM 2012, Norfolk, VA, USA, April 3-5, 2012, Proceedings
EditorsAlwyn E. Goodloe, Suzette Person
Place of PublicationBerlin, Germany
Number of pages15
ISBN (Electronic)9783642288913
ISBN (Print)9783642288906
Publication statusPublished - 27 Mar 2012
Externally publishedYes
Event4th NASA Formal Methods Symposium, NFM 2012 - Norfolk, VA, United States
Duration: 3 Apr 20125 Apr 2012

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th NASA Formal Methods Symposium, NFM 2012
Country/TerritoryUnited States
CityNorfolk, VA

Cite this