Supervisor reduction for discrete-event systems

被引：123

作者：

Su, R ^{[1
]}

Wonham, WM ^{[1
]}

机构：

[1] Univ Toronto, Edward S Rogers Sr Dept Elect & Comp Engn, Toronto, ON M5S 3G4, Canada

来源：

DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS | 2004年 / 14卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

supervisory control theory; control congruence; algorithmic supervisor reduction; minimal supervisor size estimation;

D O I：

10.1023/B:DISC.0000005009.40749.b6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In supervisory control theory (SCT) the supremal supervisor (representing the supremal controllable sublanguage) typically has a large state size (of order the product of state sizes of the plant and specification automata). In this paper, we propose an algorithm which can significantly reduce supervisor size while preserving control action. We also show that finding a supervisor of minimal size is NP-hard.

引用

页码：31 / 53

页数：23

共 12 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] FINDING ALL CLIQUES OF AN UNDIRECTED GRAPH [H] [J].

BRON, C ;

KERBOSCH, J .

COMMUNICATIONS OF THE ACM, 1973, 16 (09) :575-577

[3]

de Queiroz MH, 2002, WODES'02: SIXTH INTERNATIONAL WORKSHOP ON DISCRETE EVENT SYSTEMS, PROCEEDINGS, P377, DOI 10.1109/WODES.2002.1167714

[4]

Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation

[5]

MINHAS R, 2002, THESIS U TORONTO

[6] THE MAXIMUM CLIQUE PROBLEM [J].

PARDALOS, PM ;

XUE, J .

JOURNAL OF GLOBAL OPTIMIZATION, 1994, 4 (03) :301-328

[7]

PENA JM, 1998, P ICCAD98 CA SAN JOS

[8] STATE REDUCTION IN INCOMPLETELY SPECIFIED FINITE-STATE MACHINES [J].

PFLEEGER, CP .

IEEE TRANSACTIONS ON COMPUTERS, 1973, C 22 (12) :1099-1102

[9] SUPERVISORY CONTROL OF A CLASS OF DISCRETE EVENT PROCESSES [J].

RAMADGE, PJ ;

WONHAM, WM .

SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1987, 25 (01) :206-230

[10] ON SUPERVISOR REDUCTION IN DISCRETE-EVENT SYSTEMS [J].

VAZ, AF ;

WONHAM, WM .

INTERNATIONAL JOURNAL OF CONTROL, 1986, 44 (02) :475-491

← 1 2 →