基于最小序句子的上下文无关语言句子枚举

形式规约获取系统SAQ和一些形式化验证系统中常常需要枚举上下文无关语言的句子，现有的枚举方法较少且效率较低，以上下文无关语言L(G)的最小序句子和最大序句子为基础，从最小序句子开始按照一定的顺序扫描字符串，直至扫描到最大序句子为止，对被扫描的字符串进行判断取舍，在扫描的过程中采用削减和前瞻策略，很大程度上减少了被扫描的字符串个数，可以取得较好的时空性能，实验数据表明，基于最小序句子的枚举方法比其他上下文无关语言句子枚举方法具有更高的效率。     

一种上下文无关语言语法树的存储模式及其应用

针对上下文无关语言的句子所对应的语法树G树的表示形式提出了一种关系数据库的存储形式.这种存储形式的优点是：表示形式一致;句子分析简单;语句执行速度快.这种存储形式作为一种上下文无关语言的中间语言的形式可以直接交付解释器（抽象机）执行.同时介绍基于这种表示形式的上下文无关句子的编辑器.编辑器是基于Web的交互式语法制导生成方式实现的.这种表示与存储形式被用于一种描述过程性知识的函数式语言.     

基于上下文依赖规则覆盖的句子生成

基于规则覆盖的句子生成,是上下文无关文法句子生成的主要方法,但是它也具有局限性。最近提出的上下文依赖规则覆盖,能根据文法的内部结构不同而具有不同的分支集合,比规则覆盖的精度更高。目前,尚未见这种上下文依赖规则覆盖的句子生成算法。该文在规则覆盖的句子生成算法的基础上,实现一个基于上下文依赖规则覆盖的句子生成算法。该算法已在机器上实现并经过实验检验。     

获取上下文无关文法的一种交互式算法

本文提出一种交互式的上下文无关语言的学习算法，该算法是专门为ＳＡＱ系统设计的，所得到的文法能够自然地反映句子的内部结构，从而很容易刻划句子的含义（语义）。     

基于文法分支覆盖的短句子生成算法

提出一种上下文无关文法的句子生成算法.对于给定文法,算法生成一个满足该文法分支覆盖准则的句子集.结合长度控制、冗余消除和句子集规模控制等策略,使得生成的句子较短、无冗余、句子集规模较小.考察了算法在基于文法的软件系统的测试数据生成方面的应用情况.实验结果表明,该算法生成的测试数据具有较强的程序揭错能力,并且能够帮助测试人员提高测试速度.     

Petri网语言与传统形式语言的关系

本文介绍了一种形式语言－Ｐｅｔｒｉ网语言，并讨论了Ｐｅｔｒｉ网语言与传统形式语言（正规语言，上下文无关语言，上下文有关语言以及递归枚举语言）的关系。     

基于BERT双向预训练的图模型摘要抽取算法

近年的自动摘要算法大多是基于监督学习机制,没有考虑到人工标记语料的烦琐,并且大多数摘要模型在句子嵌入时不能结合上下文来更充分表达语义信息,忽略了文本的整体信息.针对上述问题提出了一种基于改进的BERT双向预训练语言模型与图排序算法结合的抽取式摘要模型.根据句子的位置以及上下文信息将句子映射为结构化的句子向量,再结合图排序算法选取影响程度靠前的句子组成临时摘要;为了避免得到有较高冗余度的摘要,对得到的临时摘要进行冗余消除.实验结果表明在公用数据集CNN/DailyMaily上,所提模型能够提高摘要的得分,相对于其他改进的基于图排序摘要抽取算法,该方法效果更佳.     

《计算机研究与发展》2004年（第41卷）总目次

第一期演化门限ARMA模型方法与应用代建华　董文永　李元香　潘云鹤 (1)………………………………………………………基于最小序句子的上下文无关语言句子枚举黄文集 (9)……………………………………………………………………………一种基于PID反馈控制的分时调度算法童立靖　淮晓永　李明树 (15 )…………………………………………………………IA 6 4中软件流水的寄存器需求研究林海波　李文龙　汤志忠 (2 2 )……………………………………………………………基于类型注解的认证编译器设计与实现胡荣贵　陈意云　郭　帆　张　昱 (2 8)…     

范畴文法接受语言的能力

本文研究Ades和steedman提出的范畴文法.与上下文无关文法相比较,我们讨论具有不同的约简规则集的范畴文法接受语言的能力.使用F规则和FP规则时,接受的语言恰好是上下文无关语言.使用口规则和FP规则时,接受的语言包含上下文无关语言为其真子集.使用F规则、FP规则和BP规则时,该文法不能接受某些上下文无关语言.     

推导可交换上下文无关语言

提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.     

基于产生式集划分的上下文无关语言句子生成

给出了上下文无关文法(context-free grammar,简称CFG)产生式集的一种划分方法,可将产 生式分为两类.使用一类产生式进行推导时,推导过程将无限进行下去;使用另一类进行推导 时,推导过程将迅速结束.证明了CFG句子生成过程一定是先使用一类产生式使生成的句型不 断变长、变复杂,再使用另一类产生式使句型变成句子.据此,提出了一种可控制的通用句子 生成方法.其生成一条句子的时间和空间复杂度是O(r+n),其中n是生成句子的长度或深度 限制     

上下文无关语言分析树的一种表示形式

介绍了上下文无关语言（ＣＦＬ）的句子的一种分析树表示,它适用用于一类与以往不同的ＣＦＬ的应用,即对分析树空间效率要求较高且不需标记分析树的应用,典型的就是把ＣＦＬ的句子用作算法加工对象,这种表示比传统分析树不仅空间较小,而且进行结构匹配的快速快,还介绍了这种分析树表示的实现技术。     

Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions

In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains . It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described.     

Recursive functions of context free languages (II)

In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains. It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described. This paper is based on the Technical Report ISCAS-LCS-2k-03 (SAQ Report no.30): Recursive Functions Defined on Context Free Languages (I) August 2000 with minor revisions.     

Bandpass signal formulation with hybrid implicit-explicit procedure in open regions for unmagnetized plasma

The finite-difference time-domain (FDTD) algorithm shows disadvantages in bandpass signal simulation with fine structures along a single direction. The reason is that FDTD algorithm exists the Courant–Friedrichs–Levy (CFL) condition and bases on the lowpass-sampling theorem. Based on the numerical implementation, hybrid implicit-explicit procedure and complex envelope method are introduced. As a full-wave simulation method, higher order concept is incorporated into perfectly matched layer (PML) formulation for improving absorption at boundaries of the lattice. For unmagnetized plasma simulation, piecewise linear recursive convolution method is modified according to the bandpass signal. Through numerical example, the proposed algorithm shows considerable performance during the entire simulation which can be concluded from several aspects: (1) It takes advantages of higher order concept which shows enhanced absorption. (2) The proposed algorithm can overcome the CFL condition and maintain stability with the increment of time steps. (3) It shows considerable efficiency and accuracy in simulating structures with fine details along a single direction. (4) It can alleviate time increment problem among implicit algorithms with lower CFL numbers.     

Generalizing input-driven languages: Theoretical and practical benefits

Regular languages (RL) are the simplest family in Chomsky’s hierarchy. Thanks to their simplicity they enjoy various nice algebraic and logic properties that have been successfully exploited in many application fields. Practically all of their related problems are decidable, so that they support automatic verification algorithms. Also, they can be recognized in real-time.Context-free languages (CFL) are another major family well-suited to formalize programming, natural, and many other classes of languages; their increased generative power w.r.t. RL, however, causes the loss of several closure properties and of the decidability of important problems; furthermore they need complex parsing algorithms. Thus, various subclasses thereof have been defined with different goals, spanning from efficient, deterministic parsing to closure properties, logic characterization and automatic verification techniques.Among CFL subclasses, so-called structured ones, i.e., those where the typical tree-structure is visible in the sentences, exhibit many of the algebraic and logic properties of RL, whereas deterministic CFL have been thoroughly exploited in compiler construction and other application fields.After surveying and comparing the main properties of those various language families, we go back to operator precedence languages (OPL), an old family through which R. Floyd pioneered deterministic parsing, and we show that they offer unexpected properties in two fields so far investigated in totally independent ways: they enable parsing parallelization in a more effective way than traditional sequential parsers, and exhibit the same algebraic and logic properties so far obtained only for less expressive language families.     

基于TextRank的自动摘要优化算法

在对中文文本进行摘要提取时,传统的TextRank算法只考虑节点间的相似性,忽略了文本的其他重要信息。首先,针对中文单文档,在现有研究的基础上,使用TextRank算法,一方面考虑句子间的相似性,另一方面,使TextRank算法与文本的整体结构信息、句子的上下文信息等相结合,如文档句子或者段落的物理位置、特征句子、核心句子等有可能提升权重的句子,来生成文本的摘要候选句群;然后对得到的摘要候选句群做冗余处理,以除去候选句群中相似度较高的句子,得到最终的文本摘要。最后通过实验验证,该算法能够提高生成摘要的准确性,表明了该算法的有效性。     

基于上下文语境的词义消歧方法

针对传统词义消歧方法面临的数据稀疏问题,提出一种基于上下文语境的词义消歧方法。该方法假设同一篇文章中的句子之间共享一些相同的话题,首先,抽取在同一篇文章中包含相同歧义词的句子,这些句子可以作为歧义句的上下文语境,为其中的一个歧义句子提供消歧知识;其次,通过一种无监督的词义消歧方法进行词义消歧。在真实的语料上实验结果表明,使用2个上下文语境句子,窗口大小为1时,该方法的消歧准确率比基线方法(OrigDisam)提高了3.26%。     

基于语义角色标注的汉语句子相似度算法

在语义角色标注过程中,经常需要检索相似的已标注语料,以便进行参考和分析。现有方法未能充分利用动词及其支配的成分信息,无法满足语义角色标注的相似句检索需求。基于此,本文提出一种新的汉语句子相似度计算方法。该方法基于已标注好语义角色的语料资源,以动词为分析核心,通过语义角色分析、标注句型的相似匹配、标注句型间相似度计算等步骤来实现句子语义的相似度量。为达到更好的实验效果,论文还综合比较了基于知网、词向量等多种计算词语相似度的算法,通过分析与实验对比,将实验效果最好的算法应用到句子相似度计算的研究中。实验结果显示,基于语义角色标注的句子相似度计算方法相对传统方法获得了更好的测试结果。