Model matching for finite-state machines (Q4540239)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1769464
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Model matching for finite-state machines |
scientific article; zbMATH DE number 1769464 |
Statements
Model matching for finite-state machines (English)
0 references
21 July 2002
0 references
discrete-event systems
0 references
finite-state machines
0 references
model matching
0 references
supervisory control
0 references
disturbances
0 references
maximal behaviors
0 references
0.77862227
0 references
0 references
0 references
0.7712838
0 references
0.7691741
0 references
The problem of model matching has been previously considered for linear (see \textit{B. Moore} and \textit{L. Silverman} [ibid. 17, 491-497 (1972; Zbl 0263.93033)], \textit{A. S. Morse} [ibid. 18, 346-354 (1973; Zbl 0264.93005)]) and nonlinear (\textit{M. D. Di Benedetto} [ibid. 35, 1351-1355 (1990; Zbl 0734.93039)], \textit{A. Isidori} [ibid. 30, 258-265 (1985; Zbl 0564.93032)]) continuous-time systems. The article is probably the first to address the problem for finite-state machines (FSMs), where FSM is a 5-tuple \(M=(I,O,S,\Delta,r)\) with \(I\), \(O\) the input and output alphabets, \(S\) the set of states, \(\Delta \subseteq I \times S \times S \times O\) the transition (the next state and the output) relation and \(r \in S\) the initial state. The FSM is deterministic (DFSM) or nondeterministic (NDFSM) according to a deterministic or nondeterministic transition relation \(\Delta\). Given an FSM \(M\), called the reference model, that describes some desired input-output behavior and another FSM \(M_1\), called the plant, with a given behavior, the problem of model matching is to find a compensator FSM \(M_2\), so that the behavior of the system \(M_1 \circ M_2\) matches the behavior of \(M\) (i.e. sets of their possible input/output sequences are the same). As for input and output alphabets, it is assumed that \(I_{M_2}=I_M\), \(O_{M_2}=I_{M_1}\), \(O_{M_1}=O_M\), the outputs of \(M_2\) are used as the inputs of \(M_1\), so the system \(M_1\circ M_2\) has the same inputs and outputs as \(M\). The following settings of the problem are considered. Strong FSM Model Matching. Given DFSMs \(M\), \(M_1\) and possibly NDFSM \(M_2\) the problem has a solution if and only if \(M^{-1}\) is simulated by \(M_1^{-1}\) under some simulation relation, where \(M^{-1}\), \(M_1^{-1}\) are inverse FSMs (i.e., using output labels of \(M\), \(M_1\) as their input labels). The constructive optimum solution to the problem (the FSM with a minimal number of states) is found as well. Strong FSM Model Matching with Measurable Disturbances. In this case for DFSMs \(M\), \(M_1\) and possibly NDFSM \(M_2\) it is assumed that \(I_M=I_{M_2}=(W,V)\), \(O_{M_2}=I_{M_1}=(W,U)\), \(O_M=O_{M_1}\), disturbances are described by the set \(W\). The compensator \(M_2\) can observe (measure) disturbances and passes them through without modification. The problem is reduced to the previous one. A traffic light controller is considered as an example. Strong Model Matching with a Set of Reference Models. The set of models (or nondeterministic model) is considered as NDFSM \(M\). Any deterministic behavior and the set of maximal behaviors contained in \(M\) are analyzed in this framework. Supremal Language Problem for Supervisory Control. The description of the problem is available in \textit{P. J. Ramadge} and \textit{W. M. Wonham} [SIAM J. Control Optimization 25, 206-230 (1987; Zbl 0618.93033)]. It is shown that the problem in its basic form can be solved as the strong matching problem with measurable disturbances.
0 references