A resurgent interest for grammatical inference aka automatonlearning has emerged in several intriguing areas of computer sciences such as machine learning, software engineering, robotics and internet of things. An au...
详细信息
A resurgent interest for grammatical inference aka automatonlearning has emerged in several intriguing areas of computer sciences such as machine learning, software engineering, robotics and internet of things. An automaton learning algorithm commonly uses queries to learn the regular grammar of a Deterministic Finite automaton (DFA). These queries are posed to a Minimum Adequate Teacher (MAT) by the learner (learningalgorithm). The membership and equivalence queries which the learningalgorithm may pose, are often capable of having their answers provided by the MAT. The three main categories of learningalgorithms are incremental, sequential, and complete learningalgorithms. In the presence of a MAT, the time complexity of existing DFA learningalgorithms is polynomial. Therefore, in some applications these algorithms may fail to learn the system. In this study, we have reduced the time complexity of DFA learning from polynomial to logarithmic form. For this, we propose an efficient complete DFA learningalgorithm;the Block based DFA learning through Inverse Query (BDLIQ) using block based delta inverse strategy, which is based on the idea of inverse queries that John Hopcroft introduced for state minimization of a DFA. The BDLIQ algorithm possess O(|sigma|***) complexity when a MAT is available. The MAT is also made capable of responding to inverse queries. We provide theoretical and empirical analysis of the proposed algorithm. Results show that our suggested approach for complete learning;BDLIQ algorithm, is more efficient than the ID algorithm in terms of time complexity.
The paper presents an approach to the control of black-box embedded systems by integrating automatonlearning and supervisory control theory (SCT) of discrete-event systems (DES), where automaton models of both the sy...
详细信息
The paper presents an approach to the control of black-box embedded systems by integrating automatonlearning and supervisory control theory (SCT) of discrete-event systems (DES), where automaton models of both the system and requirements are unavailable or hard to obtain. First, the system is tested against the requirements. If all the requirements are satisfied, no supervisor is needed and the process terminates. Otherwise, a supervisor is synthesized to enforce the system to satisfy the requirements. To apply SCT and automatonlearning technologies efficiently, the system is abstracted to be a finite-discrete model. Then, a $C<^>{*}$ learningalgorithm is proposed based on the classical $L<^>{*}$ algorithm to infer a Moore automaton describing both the behavior of the system and the conjunctive behavior of the system and the requirements. Subsequently, a supervisor for the system is derived from the learned Moore automaton and patched on the system. Finally, the controlled system is tested again to check the correctness of the supervisor. If the requirements are still not satisfied, a larger Moore automaton is learned and a refined supervisor is synthesized. The whole process iterates until the requirements hold in the controlled system. The effectiveness of the proposed approach is manifested through two realistic case studies. Note to Practitioners-Supervisory control theory of DES can synthesize maximally permissive supervisory controllers to ensure the correctness of software-controlled processes. The application of supervisory control theory relies on automaton models of the plant and specifications;however, the required models are often unavailable and difficult to obtain for black-box embedded systems. automatonlearning is an effective method for inferring models of black-box systems. This paper integrates the two technologies so that the supervisory control theory is applicable to the development of black-box embedded software systems. The proposed appro
暂无评论