|
Theory of computing
On the application of the calculus of positively constructed formulas for the study of controlled discrete-event systems
A. V. Davydov, A. A. Larionov, N. V. Nagul Matrosov Institute for System Dynamics and Control Theory SB RAS
Abstract:
The article is devoted to the development of an approach to solving the main problems of the theory of supervisory control of logical discrete-event systems (DES), based on their representation in the form of positively constructed formulas (PCF). We consider logical DESs in automata form, understood as generators of some regular languages. The PCF language is a complete first-order language, the formulas of which have a regular structure of alternating type quantifiers and do not contain a negation operator in the syntax. It was previously proven that any formula of the classical first-order predicate calculus can be represented as a PCF. PCFs have a visual tree representation and a natural question-and-answer procedure for searching for an inference using a single inference rule. It is shown how the PCF calculus, developed in the 1990s to solve some problems of control of dynamic systems, makes it possible to solve basic problems of the theory of supervisory control, such as checking the criteria for the existence of supervisory control, automatically modifying restrictions on the behavior of the controlled system, and implementing a supervisor. Due to some features of the PCF calculus, it is possible to use a non-monotonic inference. It is demonstrated how the presented PCF-based method allows for additional event processing during inference. The Bootfrost software system, or the so-called prover, designed to refute the obtained PCFs is also presented, and the features of its implementation are briefly described. As an illustrative example, we consider the problem of controlling an autonomous mobile robot.
Keywords:
positively constructed formula, automated theorem proving, prover, discrete event system, supervisory control.
Received: 02.02.2024 Revised: 08.02.2024 Accepted: 14.02.2024
Citation:
A. V. Davydov, A. A. Larionov, N. V. Nagul, “On the application of the calculus of positively constructed formulas for the study of controlled discrete-event systems”, Model. Anal. Inform. Sist., 31:1 (2024), 54–77
Linking options:
https://www.mathnet.ru/eng/mais815 https://www.mathnet.ru/eng/mais/v31/i1/p54
|
Statistics & downloads: |
Abstract page: | 38 | Full-text PDF : | 26 | References: | 13 |
|