A Machine Learning based Approach to Verifying Controllability of Discrete Event Systems

In this paper, we consider the problem of controllability verification of discrete-event systems (DESs). The model of a concerned DES is unknown, whereas a set of data D containing a finite set of strings describing the behaviors of the DES is available. First, we investigate necessary and sufficient conditions on the informativity of data D, i.e., under what conditions D contains sufficient information such that a control specification K is controllable with respect to all DESs that can generate data D. Next, we show that data-informativity verification can be regarded as a classification problem which can be solved easily by using a classification algorithm of machine learning. Let D<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</inf> be the controllable language generated by data D with respect to specification K. We treat D<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</inf> and K as training and test data, respectively. After obtaining a classification model using the training data, we can determine whether D is informative by querying the accuracy against the obtained classification model using the test data. Specifically, if the accuracy is less than 100%, then the given data D is not informative. Experimental results show the effectiveness of the proposed approach.