Coinduction in Control of Partially Observed Discrete-Event Systems

Coalgebra and coinduction provide new results and insights for the supervisory control of discrete-event systems (DES) with partial observations. In the case of full observations, coinduction has been used to define a new operation on languages called supervised product, which represents the tuple of languages of the supervised system. The first language acts as a supervisor and the second as an open-loop system (plant). We show first that the supervised product is equal to the infimal controllable superlanguage of the supervisor's (specification) language with respect to the plant language. This can be generalized to the partial observation case, where the supervised product is shown to be equal to the infimal controllable and observable superlanguage. A modification on the supervised product is presented, which corresponds to the control policy for with the issue of observability is separated from the issue of controllability. The operation defined by coinduction is shown to be equal to the infimal observable superlanguage.     

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.     

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.     

Supervisory Control of a Class of Concurrent Discrete Event Systems Under Partial Observation

In this paper, we study supervisory control of a class of discrete event systems with simultaneous event occurrences, which we call concurrent discrete event systems, under partial observation. The behavior of the system is described by a language over the simultaneous event set. First, we prove that L_m(G)-closure, controllability, observability, and concurrent well-posedness of a specification language are necessary and sufficient conditions for the existence of a nonblocking supervisor. Next, we synthesize a supervisor that achieves the infimal closed, controllable, observable, and concurrently well-posed superlanguage of a specification language. Finally, we synthesize a supervisor that achieves a maximal closed, controllable, observable, and concurrently well-posed sublanguage of a closed specification language.     

Petri网语言的Pumping引理

Petri网语言是Petri网理论的重要组成部分,也是系统行为分析的一种重耍的工具．Petri网语言的Pumping引理反映了Petri网语言的共性,可用来证明某些语言不是Petri网语言,已经证明,当一个Petri网语言可被某个有界Petri网产生时,此语言是正规语言,因此,正规语言的Pumping引理对此语言是有效的,但正规语言的Pumping引理并小适用于所有的Petrl网语言．文中给出了一种Petri网语言的Pumping引理,证明其对任意无空标注的Petri网语言都有效,并且＋正规语言的Pumping引理是此引理的一种特殊形式．利用此Pumping引理可以证明某些语言是不能由Petri网产生的。     

Splicing systems and regularity

A direct and constructive proof is given that every regular language is the homomorphic image of a splicing language as defined by Head. The class of splicing languages involved have a particularly simple presentation and are regular. Also presented are some examples which demonstrate the relation of the class of splicing languages to that of regular languages and an example of a regular language which is not a splicing language.     

Optimal control of infinite horizon partially observable decision processes modelled as generators of probabilistic regular languages

Decision processes with incomplete state feedback have been traditionally modelled as partially observable Markov decision processes. In this article, we present an alternative formulation based on probabilistic regular languages. The proposed approach generalises the recently reported work on language measure theoretic optimal control for perfectly observable situations and shows that such a framework is far more computationally tractable to the classical alternative. In particular, we show that the infinite horizon decision problem under partial observation, modelled in the proposed framework, is λ-approximable and, in general, is not harder to solve compared to the fully observable case. The approach is illustrated via two simple examples.     

二元文法

在正规文法的基础上,通过增加一个约束变量集合,给出了二元文法的定义,证明了二元文法与袋自动机的等价性,定义了平衡推导、递增推导、递减推导和传递推导,证明了它们与不变重复序列、增重复序列、减重复序列和传递重复序列之间的关系,并且给出判定一个二元文法所产生语言（袋语言）分别是正规语言、上下文无关语言或上下文文有关语言的充分条件。     

Palindrome words and reverse closed languages

A word which is equal to its mirror image is called a palindrome word. Any language consisting of palindrome words is called a palindrome language. In this paper we investigate properties of palindrome words and languages. We show that there is no dense regular language consisting of palindrome words. A language contains all the mirror images of its elements is called a reverse closed language. Clearly, every palindrome language is reverse closed. We show that whether a given regular or context-free language is reverse closed is decidable. We study certain properties concerning reverse closed finite maximal prefix codes in this paper. Properties of languages that commute with reverse closed languages are investigated too.     

Characterization of co-observable languages and formulas for their super/sublanguages

We present fixed-point based characterization of several classes of co-observable languages that are of interest in the context of decentralized supervisory control of discrete-event systems, including C&P /spl or/ D&A co-observable languages, C&P co-observable languages, and D&A co-observable languages. We also provide formulas for computing super/sublanguages for each of these classes. In cases where the class of co-observable languages is not closed under intersection/union, we provide upper/lower bound of the super/sublanguage formula we present. The computation of super/sublanguages and also computation of their upper/lower bounds has lead to the introduction of other classes of co-observable languages, namely, strongly C&P co-observable languages, strongly D&A co-observable languages, locally observable languages, and strongly locally observable languages. Fixed-point based characterization of all the above language classes is also given, and their closure under intersection/union is investigated. We also study whether the fixed-point operator preserves prefix closure, relative closure (also called L/sub m/(G)-closure), and controllability.     

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

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

IFS与L系统的统一描述语言及其分类

为了更高效地表示分形图形,依据形式语言的文法结构及正则表达式的文法规则,通过引入代数运算,提出了一个能够对L系统和迭代函数系统(IFS)统一描述的语言代数系统。根据语言代数系统产生式的文法规则,将此系统的产生式集划分为五类。结合分形理论,此语言代数系统着重将DOL系统、迭代函数系统(IFS)、带凝聚集迭代函数系统(凝聚IFS)、随机迭代函数系统(IFSP)和再归迭代函数系统(RIFS)等进行描述,同时用此系统的正则表达式方程解将分形吸引子进行代数表示,并给出一些实例。通过实例表明,分形图形可以用该语言代数系统简单、明了、高效地表示。     

A language measure for partially observed discrete event systems

Recent literature has introduced and validated a signed real measure of regular languages for quantitative analysis and synthesis of discrete-event supervisory (DES) control systems, where all events are assumed to be observable. This paper presents a modification of the language measure for supervisory control under partial observation and shows how to generalize the analysis when some of the events may not be observable at the supervisory level. In the context of DES control synthesis, the language measure of partially observable discrete-event processes is expressed in a closed form which is structurally similar to that of completely observable discrete-event processes. Examples are provided to elucidate the concept of DES control under partial observation.     

A grammatical inference for harmonic linear languages

We propose an effective algorithm to infer linear grammars from given finite sample sets. It is shown that the algorithm is complete for harmonic linear languages being a superclass of regular languages. A necessary and sufficient condition under which the algorithm converges to an expected grammar is given.     

Supervisory control of timed discrete event systems under partial observation based on activity models and eligible time bounds

To avoid the state–space explosion by including tick events in timed discrete event systems (DESs) under partial observation, a notion of eligible time bounds is introduced and based on the notion, controllability and observability conditions of languages are presented. In particular, this paper shows that these controllability and observability conditions are necessary and sufficient for the existence of a supervisor to achieve the given language specification.     

Some Properties of Iterated Languages

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses of natural language quantifiers. We also determine the state complexity of iteration of regular languages.     

The infimal closed controllable superlanguage and its applicationin supervisory control

The supervisory control of discrete-event systems is investigated for the case in which nonblocking solutions are deemed inadequate because they are too conservative. For this purpose the infimal closed controllable superlanguage of a given language is studied. Two characterizations of the superlanguage are given, some of its properties are presented, and algorithms for its computation in the general case and in the regular case are proposed. An algorithm for the computation of the supremal controllable sublanguage is presented. It is shown that the computation of the infimal closed controllable superlanguage plays a central role in problems that involve a tradeoff between satisficing and blocking. The completely satisficing solution in supervisory control is characterized, and a general control problem called the supervisory control problem with blocking is introduced     

On inverse deterministic pushdown transductions

Classes of source languages which can be mapped by a deterministic pushdown (DPDA) transduction into a given object language (while their complement is mapped into the complement of the object language) are studied. Such classes of source languages are inverse DPDA transductions of the given object language. Similarly for classes of object languages. The inverse DPDA transductions of the Dyck sets are studied in greater detail: they can be recognized in deterministic storage (log n)' but do not comprise all context free languages; their emptiness problem is unsolvable and their closure under homomorphism constitutes the r.e. sets. For each object language L we can exhibit a storage hardest language for the class of inverse DPDA transductions of L; similarly for the classes of regular, deterministic context free, and context free object languages. Last, we classify the classes of inverse DPDA transductions of the regular, deterministic context free, context free and deterministic context sensitive languages.     

Decidability of operation problems for T0L languages and subclasses

We investigate the decidability of the operation problem for T0L languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable. The situation changes for unary 0L languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.     

语言附着的句法结构

本文研究语言Ｌ的附着Ａｄｈ（Ｌ）的句法结构，借助于Ｌ的语法分析树，我们分析了Ａｄｈ（Ｌ）的句法特征，提出并证明了正规语言和上下文无关语言附着的叠代定理，从而解决了这两类语言的附着的句法结构问题。另外，应用引理证明了某些附着不是正规语言的附着或上下文无关语言的附着。