A note on deciding controllability in pushdown systems

Consider an event alphabet /spl Sigma/. The supervisory control theory of Ramadge and Wonham asks the question, given a plant model G, with language K L/sub M/(G)/spl sube//spl Sigma//sup */ and another language K/spl sube/ L/sub M/(G), is there a supervisor /spl psi/ such that L/sub M/(/spl psi//G)=K. Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L/sub M/(G). They showed that when G is a finite state automaton and K is a regular language (also generated by a finite state automaton), then the controllability property was decidable for K. The class of languages generated by pushdown automata properly includes the regular languages. They are accepted by finite state machines coupled with pushdown stack memory. This makes them interesting candidates as supervisory languages, since the supervisor will have nonfinite memory. In this note, we show the following: i) If S is a specification given by a deterministic pushdown automaton and L is generated by a finite state machine, then there is an algorithm to decide whether K=S/spl cap/L is controllable with respect to L. ii) It is undecidable for an arbitrary specification S generated by a nondeterministic pushdown automaton and plant language L generated by a finite state machine whether K=S/spl cap/L is controllable with respect to L.     

On the language generated under fully decentralized supervision

This paper studies the language generated under fully decentralized supervision proposed by Kozak and Wonham (1995). The author assumes that desirable behavior is specified as a closed language. A closed-form expression for the language generated under fully decentralized supervision is presented. It is shown that the generated language is larger than the supremal closed, controllable, and strongly decomposable sublanguage. Moreover, a necessary and sufficient condition is derived for the generated language to be the supremal closed and controllable sublanguage     

Bisimulation, the Supervisory Control Problem and Strong Model Matching for Finite State Machines

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.     

On supervisory control of sequential behaviors

The authors address the supervisory synthesis problem of controlling the sequential behaviors of discrete-event dynamical systems (DEDSs) under complete and partial information through the use of synchronous composition of the plants and the supervisors. The authors present the notion of complete languages, discuss some of its algebraic properties, and show its close relation to ω-languages. The authors prove that the supremal (closed) complete and controllable sublanguage of a given language exists, and present an algorithm to compute it. They present a closed-form expression for the supremal ω-controllable sublanguage of a given ω-language in terms of the supremal (closed) complete and controllable sublanguage. This closed-form expression suggests that certain operations on a given ω-language can alternatively be achieved by performing certain other similar operations on its prefix (which is a finite language) and then taking the limit (to obtain the desired ω-language). A necessary and sufficient condition for the existence of a supervisor in case of partial observation is presented in terms of ω-observability. Notion of ω-normality is also introduced, and a closed-form expression for the supremal ω-normal sublanguage, in terms of the supremal closed, complete, and normal sublanguage, is presented     

A New Class of Supervisors for Timed Discrete Event Systems Under Partial Observation

Brandin and Wonham have developed a supervisory control framework for timed discrete event systems (TDESs) in order to deal with not only logical specifications but also temporal specifications. Lin and Wonham have extended this framework to the partial observation case, and presented necessary and sufficient conditions for the existence of a nonblocking supervisor under partial observation. In this paper, we define a new class of supervisors for TDESs under partial observation. We then present necessary and sufficient conditions for the existence of a nonblocking supervisor defined in this paper. These existence conditions of our supervisor are weaker than those of Lin and Wonham's supervisor. Note, however, that the price that must be paid to weaken the existence conditions is the higher computational cost. Moreover, given a closed regular language, we study computation of a sublanguage that satisfies the existence conditions of our supervisor. We present an algorithm for computing such a sublanguage larger than the supremal closed, controllable, and normal sublanguage.     

Characterizations and effective computation of supremal relatively observable sublanguages

Recently we proposed relative observability for supervisory control of discrete-event systems under partial observation. Relative observability is closed under set unions and hence there exists the supremal relatively observable sublanguage of a given language. In this paper we present a new characterization of relative observability, based on which an operator on languages is proposed whose largest fixpoint is the supremal relatively observable sublanguage. Iteratively applying this operator yields a monotone sequence of languages; exploiting the linguistic concept of support based on Nerode equivalence, we prove for regular languages that the sequence converges finitely to the supremal relatively observable sublanguage, and the operator is effectively computable. Moreover, for the purpose of control, we propose a second operator that in the regular case computes the supremal relatively observable and controllable sublanguage.     

Controllability and control-invariance in discrete-event systems

Recently, for discrete-event systems modelled by automata, Ramadge and Wonham (1987 a, b) have proposed two control techniques called ‘supervisory control’ and ‘state feedback logic’. If control specifications are given in terms of predicates on the set of states, both techniques are applicable. This paper discusses the relationship between these techniques. It is shown that the language accepted by the discrete-event system with maximally permissive feedback is equal to the supremal controllable language if the predicate is control invariant. Moreover, it is shown that the predicate is control invariant if there exists a controllable language with a certain condition on the set of reachable states, but the converse does not hold in general     

An algorithm for computing the mask value of the supremal normalsublanguage of a legal language

We consider the problem of finding the mask value of the supremal normal sublanguage L_R of some given language L. We describe a straightforward algorithmic solution that can be applied to existing off-line procedures for determining the supremal controllable and normal sublanguage of L and that does not require an explicit calculation of L _R. This problem is fundamental because it is related to the supervisory control problem under partial observation. Our algorithm applies only to closed languages     

Formulas for a class of controllable and observable sublanguages larger than the supremal controllable and normal sublanguage

In this paper, we give some new methods for synthesis of controllers of discrete event dynamical systems (DEDS) with partial event informations. Given a regular target language L, we construct some effective computable algorithms for computing the controllable and observable sublanguages of L. We show that any one of these controllable and observable sublanguages obtained by our algorithms is larger than the supremal controllable and normal sublanguage of L.     

Online supervisor synthesis for partially observed discrete-eventsystems

A partial information supervisor that generates a class of closed controllable and observable sublanguages of a specified “legal” language is presented. This supervisor has the following features: 1) it can be implemented online (i.e., the disabled event set need only be computed once upon each event observation); 2) the computations of the disabled event set can be performed in O(mn) worst case complexity, where a is the number of states in the legal language generator and m is the number of events; 3) an online supervisor presented previously by Heymann and Lin (1993) is a special case of the new supervisor; and 4) all the languages generated by the new supervisor contain the supremal closed controllable and normal (supCCN) sublanguage of the legal language (in fact, they contain a language developed by Fa et al. (1993) that was shown to contain the supCCN sublanguage)     

Relative coobservability for decentralised supervisory control of discrete-event systems

In this paper, we study the concept of relative coobservability in decentralised supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralised setup to a decentralised one. A fundamental concept in decentralised supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present a language-based algorithm to compute this supremal sublanguage; the algorithm allows straightforward implementation using off-the-shelf algorithms. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.     

非阻塞监控器设计中的语言优化方法

本文研究在设计非阻塞监控器时所涉及到的语言的优化方法，首先给出了Ｌｍ（Ｇ）闭语言的计算公式，然后提出了能控Ｌｍ（Ｇ）闭子语言的逐级优化途径，对于目前获得的部分优化语言的封闭解进行了总结，并对各语言类之间的关系进行了分析。     

Observability and decentralized control of fuzzy discrete-event systems

Fuzzy discrete-event systems as a generalization of (crisp) discrete-event systems have been introduced in order that it is possible to effectively represent uncertainty, imprecision, and vagueness arising from the dynamic of systems. A fuzzy discrete-event system has been modeled by a fuzzy automaton; its behavior is described in terms of the fuzzy language generated by the automaton. In this paper, we are concerned with the supervisory control problem for fuzzy discrete-event systems with partial observation. Observability, normality, and co-observability of crisp languages are extended to fuzzy languages. It is shown that the observability, together with controllability, of the desired fuzzy language is a necessary and sufficient condition for the existence of a partially observable fuzzy supervisor. When a decentralized solution is desired, it is proved that there exist local fuzzy supervisors if and only if the fuzzy language to be synthesized is controllable and co-observable. Moreover, the infimal controllable and observable fuzzy superlanguage, and the supremal controllable and normal fuzzy sublanguage are also discussed. Simple examples are provided to illustrate the theoretical development.     

受控离散事件过程（CDEP）的一种代数分析方法

本文在文［１～３］的基础上，提出了受控离散事件过程（ＣＤＥＰ）的一种代数分析方法，弥补了Ｒａｍａｄｇｅ和Ｗｏｎｈａｍ［１～３］的理论对具体系统的应用缺乏可操作性的缺陷，使得对ＣＤＥＰ动态过程的分析变得更为直观，同时也使控制器的设计过程更具可操作性．     

On the supremal controllable sublanguage in the discrete-eventmodel of nondeterministic hybrid control systems

This paper is concerned with the logical control of hybrid control systems (HCS). It is assumed that a discrete-event system (DES) plant model has already been extracted from the continuous-time plant. The problem of hybrid control system design can then be solved by applying logical DES controller synthesis techniques to the extracted DES plant. Traditional DES synthesis methods, however, are not always applicable since the extracted plant DES will often exhibit nondeterministic transitions. This paper presents an extension of certain DES controller synthesis techniques to the nondeterministic control automaton found in HCS. In particular, this paper derives a formula computing the supremal controllable sublanguage of a given specification language under the assumption that the DES plant exhibits nondeterministic transitions     

A MODIFIED METHOD FOR SUPERVISOR SPECIFICATION AND SYNTHESIS OF A CLASS OF DISCRETE EVENT SYSTEMS

In this paper, a model‐refining method is proposed to alleviate the complexity involved in specification interpretation of DES control problems. The legal constraint language is defined in terms of illegal states and events in contrast with constructing the automaton of the specification language. This method could provide a more intuitive view of the DES control problem and would be suitable for practical implementation. Two examples, which have commonly been used in the literature, are employed to show the efficiency of the proposed method. Further, under this framework, it is shown that the supremal controllable sublanguage can take a simpler form based on the concept of an illegal state set. A state‐based supervisor synthesis procedure is presented, and a simple example is provided.     

On-line control of partially observed discrete event systems

It is well known that the design of supervisors for partially observed discrete-event systems is an NP-complete problem and hence computationally impractical. Furthermore, optimal supervisors for partially observed systems do not generally exist. Hence, the best supervisors that can be designed directly for operation under partial observation are the ones that generate the supremal normal (and controllable) sublanguage. In the present paper we show that a standard procedure exists by which any supervisor that has been designed for operation under full observation, can be modified to operate under partial observation. When the procedure is used to modify the optimal full-observation supervisor (i.e., the one that generates the supremal controllable language), the resultant modified supervisor is at least as efficient as the best one that can be designed directly (that generates the supremal normal sublanguage). The supervisor modification algorithm can be carried out on-line with linear computational complexity and hence makes the control under partial observation a computationally feasible procedure.     

On computation of supremal controllable, normal sublanguages

In this paper, we present an algorithm for the computation of the controllable, normal sublanguage of a given language, encountered in the solution of the supervisory control of discrete-event systems under partial observation. The algorithm produces the desired result under certain assumptions on the plant and the event projection map. In particular, the plant has to be nonblocking. The advantage of the algorithm over the solution available in the literature is that it does not involve iterations on the supremal controllable sublanguage and supremal normal sublanguage operators.     

A modified normality condition for decentralized supervisory control of discrete event systems

In this paper, we study nonblocking decentralized supervisory control of discrete event systems. We introduce a modified normality condition defined in terms of a modified natural projection map. The modified normality condition is weaker than the original one and stronger than the co-observability condition. Moreover, it is preserved under union. Given a marked language specification, there exists a nonblocking decentralized supervisor for the supremal sublanguage which satisfies L_m(G)-closure, controllability, and modified normality. Such a decentralized supervisor is more permissive than the one which achieves the supremal L_m(G)-closed, controllable, and normal sublanguage.     

Supervisory control of deterministic Petri nets with regularspecification languages

Algorithms for computing a minimally restrictive control in the context of supervisory control of discrete-event systems have been well developed when both the plant and the desired behaviour are given as regular languages. In this paper the authors extend such prior results by presenting an algorithm for computing a minimally restrictive control when the plant behaviour is a deterministic Petri net language and the desired behaviour is a regular language. As part of the development of the algorithm, the authors establish the following results that are of independent interest: i) the problem of determining whether a given deterministic Petri net language is controllable with respect to another deterministic Petri net language is reducible to a reachability problem of Petri nets and ii) the problem of synthesizing the minimally restrictive supervisor so that the controlled system generates the supremal controllable sublanguage is reducible to a forbidden marking problem. In particular, the authors can directly identify the set of forbidden markings without having to construct any reachability tree