Bisimulation, the supervisory control problem and strong model matching for finite state machines

被引:61
作者
Barrett, G [1 ]
Lafortune, S [1 ]
机构
[1] Univ Michigan, Dept Elect Engn & Comp Sci, Ann Arbor, MI 48109 USA
来源
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS | 1998年 / 8卷 / 04期
基金
美国国家科学基金会;
关键词
supervisory control; bisimulation; model matching; controllability;
D O I
10.1023/A:1008301317459
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
A fundamental relationship between the controllability of a language with respect to another language and a set of uncontrollable events in the Supervisory Control Theory initiated by (Ramadge and Wonham, 1989) and bisimulation of automata models is derived. The theoretical results relating bisimulation to controllability support an efficient solution to the Basic Supervisory Control Problem. Using (Fernandez, 1990) generalization of the partition refinement algorithm of (Paige and Tarjan, 1987), it is possible to find a partition which represents the supremal controllable sublanguage of an automaton with respect to the language of another automaton and a set of events in a worst-case running time of O(m log(n)), where m is the number of transitions and n is the number of states. Utilizing the bisimulation property of language controllability and derived relationships between automata languages and input/output finite-state machine behaviors, a precise relationship is formally derived between Supervisory Control Theory and the system-theoretic problem posed by (DiBenedetto et al., 1994) called Strong Input/Output FSM Model Matching. Specifically, it is proven that in deterministic settings instances of each problem can be mapped to the other framework and solved.
引用
收藏
页码:377 / 429
页数:53
相关论文
共 28 条
[1]  
[Anonymous], 1993, INTRO DIGITAL LOGIC
[2]  
Arnold A., 1994, FINITE TRANSITION SY
[3]  
Baeten J.C.M., 1990, Cambridge Tracts in Theoretical Computer Science, V18
[4]  
Barrett G, 1997, P AMER CONTR CONF, P2337, DOI 10.1109/ACC.1997.609068
[5]  
BARRETT G, 1996, P 34 ANN ALL C COMM
[6]   VARIABLE LOOKAHEAD SUPERVISORY CONTROL WITH STATE INFORMATION [J].
BENHADJALOUANE, N ;
LAFORTUNE, S ;
LIN, F .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1994, 39 (12) :2398-2410
[7]  
BLOOM B, 1988, P 15 ANN SIGACT SIGP
[8]  
CASSANDRAS CG, 1995, TRENDS IN CONTROL, P217
[9]  
Di Benedetto M. D., 1995, Proceedings of the Third European Control Conference. ECC 95, P2027
[10]  
DiBenedetto MD, 1995, PROCEEDINGS OF THE 34TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-4, P422, DOI 10.1109/CDC.1995.478834