基于完备剩余格值逻辑的自动机和文法理论

初步建立基于完备剩余格值逻辑自动机与文法理论的基本框架。引入l值正则文法的概念,证明了任意l值自动机识别的语言等价于某种l值正则文法所生成的语言,反之,任意l值正则文法所生成的语言等价于某种l值自动机识别的语言。获得l值自动机及被l值自动机识别的语言的连接问题刻画。特别地,建立l值和L值泵引理,并得到l值语言的判定性刻画。最后,揭示带ε移动的l值自动机与不带ε移动的l值自动机之间的两个等价关系。     

Petri网语言的Pumping引理

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

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

一种新的正则语言的判定方法

针对当前的一些正则语言的判断方法,本文指出了其中的不足之处,在右同余等概念的基础上,通过在语言的符号集中引入等价关系,提出了判断某一给定语言是否是正则语言的代数判定定理,并与原有方法进行了对比。     

上下文无关Petri网语言的Pumping引理

Petri网语言可分为正规Petri网语言、上下文无关Petri网语言和Petri网语言三类,Pumping引理反映了一类语言的共性.对于正规Petri网语言类和Petri网语言类都已给出了其相应的Pumping引理,而对于上下文无关Petri网语言类的Pumping引理却一直未给出.本文通过分析上下文无关Petri网语言的结构性质,给出了上下文无关Petri网语言的Pumping引理,并且正规Petri网语言的Pumping引理是上下文无关Petri网语言的Pumping引理的一种特殊形式,而上下文无关Petri网语言的Pumping引理又是Petri网语言Pumping引理的一种特殊形式,从而完整地解决了三类Petri网语言Pumping引理以及它们之间的关系.     

上下文无关语言的可重复序列及其性质

通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.     

可交换上下文无关文法

本文提出了可交换上下文无关文法及其该文法产生的语言——可交换上下文无关语言，证明了正规语言类是可交换上下文无关语言类的一个子集，而可交换上下文无关语言类是上下文无关语言类的一个子集；讨论了可交换上下文无关语言的结构特点，并给出了可交换上下文无关语言的Pumping引理。     

用模块模型检查的方法来证明进程的正则网络的若干经验

提供了一个使用同步描述性语言ＬＵＳＴＲＥ的例子，这个例子是关于使用此语言来描述，说明和验证一个资源协调器（这是一种正则的网络硬件设备）程序及性质都可以用ＬＵＳＴＲＥ来表达的事实可以被用来作归纳验证，验证可通过模型检查来进行。     

具有反馈增益不确定的Delta算子系统H∞控制

基于线性矩阵不等式（LMI）方法，研究Delta算子系统状态反馈增益具有加性不确定时的H∞非脆弱控制器的设计问题．给出既能保证闭环Delta算子系统稳定，又有一定H∞性能的充分必要条件．利用相关引理把该充分必要条件转化为LMI形式．数值算例表明。所提出的设计方法是有效的．     

一类高速采样不确定系统的鲁棒H∞滤波器设计

研究含有多面体参数摄动Delta算子系统的鲁棒H∞滤波问题．基于Delta算子系统有界实引理，提出了新的参数依赖型鲁棒H∞性能准则．利用该性能准则，采用线性矩阵不等式技术推导了此类系统全阶鲁棒H∞滤波器存在的充分条件，并通过求解一个凸优化问题来设计滤波器．与基于二次稳定的滤波方案相比，该方法具有较小的保守性．最后以数值示例验证了所提出方法的可行性．     

A pumping lemma for random permitting context languages

Random context grammars belong to the class of context-free grammars with regulated rewriting. Their productions depend on context that may be randomly distributed in a sentential form. Context is classified as either permitting or forbidding, where permitting context enables the application of a production and forbidding context inhibits it. For random context languages of finite index a generalization of the well-known pumping lemma for context-free languages has been proven. We drop the finite index restriction and concentrate on non-erasing grammars that use permitting context only. We prove a pumping lemma for their languages that generalizes and refines the existing one, and show that these grammars are strictly weaker than the non-erasing random context grammars.     

Extensions of sokolowski's theorem to prove languages are not context free or not regular

An extension of a theorem of Sokolowski's is given which is more generally applicable and illustrated by showing several languages are not context free. This is then modified to prove a similar kind of theorem for regular languages.     

Permutations are not context-free: An application of the interchange lemma

Let x be a nonempty string and x? another string with the same characters as x, but possibly in a different order. A string of the form xx? is called a permutation. A permutation-containing string is of the form wxx?y. The Interchange Lemma for context-free languages [11] is used to show that the set of permutation-containing strings over a 16 character alphabet is not context-free. The application of the lemma is important since other techniques, such as the pumping lemma and Ogden's lemma cannot show that the set is not context-free. Finally, a collection of open problems is given.     

New versions of Barbalat’s lemma with applications

This note presents a set of new versions of Barbalat’s lemma combining with positive (negative) definite functions. Based on these results, a set of new formulations of Lyapunov-like lemma are established. A simple example shows the usefulness of our results.     

广义时滞系统的时滞相关型H∞控制

研究了广义时滞系统的时滞相关型H_∞控制问题.首先通过引入一个新的Lyapunov-Krasovskii泛函,以严格线性矩阵不等式的形式,得到了广义时滞系统的一个新的有界实引理.在此基础上,设计了使得闭环系统正则、无脉冲和稳定,且满足H_∞性能界的时滞相关型H_∞控制器,并给出了控制器增益的显式表示.最后的算例表明了本文方法具有更小的保守性.     

The Use of Lemmas in the Model Elimination Procedure

When the model elimination (ME) procedure was first proposed, the notion of lemma was put forth as a promising augmentation to the basic complete proof procedure. Here the lemmas that are used are also discovered by the procedure in the same proof run. Several implementations of ME now exist, but only a 1970s implementation explicitly examined this lemma mechanism, with indifferent results. We report on the successful use of lemmas using the METEOR implementation of ME. Not only does the lemma device permit METEOR to obtain proofs not otherwise obtainable by METEOR, or any other ME prover not using lemmas, but some well-known challenge problems are solved. We discuss several of these more difficult problems, including two challenge problems for uniform general-purpose provers, where METEOR was first in obtaining the proof. The problems are not selected simply to show off the lemma device, but rather to understand it better. Thus, we choose problems with widely different characteristics, including one where very few lemmas are created automatically, the opposite of normal behavior. This selection points out the potential of, and the problems with, lemma use. The biggest problem normally is the selection of appropriate lemmas to retain from the large number generated.