量子上下文无关文法的代数性质

提出了量子上下文无关文法（l-VCFG）的概念,并研究了其具有的代数性质;证明了量子上下文无关文法（l-VCFG）和Chomsky范式文法（l-VCNF）以及Greibach范式文法（l-VGNF）的相互等价性;详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。     

基于Earley剖析的多功能雷达文法参数估计算法

针对基于随机上下文无关文法(Stochastic Context-Free Grammar,SCFG)建模的多功能雷达(Multi-Function Radars,MFR)参数估计问题的研究,在原有Inside-Outside(IO)算法和Viterbi-Score(VS)算法的基础上,提出一种基于Earley剖析的多功能雷达文法参数估计算法——EIO算法。该算法将IO算法与Earley剖析相结合,通过对截获的雷达数据进行预处理,可以处理任意形式的文法产生式,对文法产生式概率进行学习,从而实现MFR文法参数估计。通过理论分析和实验仿真,EIO算法可以在减少计算复杂度、记忆复杂度和运行时间的同时,有效保持文法参数估计精度,论证了方法的正确性和有效性。     

基于随机无穷自动机的多功能雷达辐射源识别方法

针对基于随机上下文无关文法（SCFG）建模的多功能雷达（MFR）辐射源识别问题,提出了一种基于随机无穷自动机（SISA）的MFR辐射源识别方法。在文法建模的基础上,对“水星”MFR控制模块文法产生式和系统特征文法产生式进行重新构造生成SCFG,利用SCFG构造随机无穷自动机作为识别器,从而实现对测量辐射源的识别。通过理论分析和实验仿真得出：该方法能实现对MFR辐射源的识别;在一定范围内,通过增加文法产生式个数,可以提高平均识别率,且识别性能优于通过SCFG构造的随机下推自动机（SPDA）。实验结果表明了该方法的正确性和有效性。     

自动提取词汇化树邻接文法

提出了一种从宾州中文语料库中自动提取词汇化树邻接文法(LTAG)的算法。该算法的主要思想是从词汇化树库中归纳出三种类型的词汇化树,然后利用了中心词驱动短语结构文法的方法从语料库自动提取结构合理的词汇化树;最后由语言规则对不合法的词汇化树进行过滤。与手工创建词汇化树邻接文法相比,它需要较少的人力,并且避免了人工创建词汇化树可能造成的遗漏或不一致现象。     

面向中国学生的英语书面语动词形式错误自动检查——基于链语法的研究

该研究以型式语法为理论基础,通过链语法形式化语法体系对动词型式进行了形式化,并对链语法动词词典进行了重构,旨在构建一个更好的面向中国学生的英语书面语动词形式错误检查系统。测试结果显示,重构后链语法词典的查错性能和句法分析能力得到提高。对错句检查的召回率比原词典提高了4.5%,准确率提高了15.7%;对本族者正确分析句子的准确率提高了12.2%。研究表明,该研究所基于的语言学理论(动词型式语法)和形式模型(链语法)可以较好地适用于中国学生书面英语动词形式错误检查系统的构建。     

基于合一的链接文法

以词汇主义形式语法为基础,建立了链接文法与合一理论相结合的句法分析新方法.在封闭测试中,基于合一的链接文法句法分析精确率和召回率相比传统链接文法分别提高了9.6%和14.1%.实验表明方法具有一定独创性和高效性.     

支持中文句法结构套叠的组合范畴语法

词组入句时发生语法性质转变,词组的句法范畴就应该转换,这种转换依赖词组作为整体进入更大词组的结构需要。要解释这种现象,组合范畴语法应该增加相应的转换规则。从集合论角度看,汉语有名词—动词—形容词依次包含关系,由此可归纳基本句法结构之间的转类套叠。在类有定职的前提下,得出转类套叠对应的范畴转换规则,形成有范畴转换机制的组合范畴语法C²-CCG。研究表明这种基于词组本位的形式语法有希望解释中文句法中各种转类套叠。     

句法标注的一般模型与参数分析

句法标注是语料标注的重点、难点所在,必须以一定的句法理论为基础。短语结构语法和依存语法是句法标注的基础理论,彼此却有很大的不同。本文以形式化为目标,提出句法标注的一般模型,分析比较两种句法标注的参数异同,深刻揭示了基于短语结构语法和基于依存语法的句法标注与一般模型之间的关系,并提出阅读依存中心原则,力图解决基于依存语法的句法标注难以标注缺省结构的问题。     

A survey of grammatical inference methods for natural language learning

The high complexity of natural language and the huge amount of human and temporal resources necessary for producing the grammars lead several researchers in the area of Natural Language Processing to investigate various solutions for automating grammar generation and updating processes. Many algorithms for Context-Free Grammar inference have been developed in the literature. This paper provides a survey of the methodologies for inferring context-free grammars from examples, developed by researchers in the last decade. After introducing some preliminary definitions and notations concerning learning and inductive inference, some of the most relevant existing grammatical inference methods for Natural Language are described and classified according to the kind of presentation (if text or informant) and the type of information (if supervised, unsupervised, or semi-supervised). Moreover, the state of the art of the strategies for evaluation and comparison of different grammar inference methods is presented. The goal of the paper is to provide a reader with introduction to major concepts and current approaches in Natural Language Learning research.     

Parallel parsing of Tree Adjoining Grammars on the Connection Machine

This paper describes a parsing algorithm for Tree Adjoining Grammar (TAG) and its parallel implementation on the Connection Machine. TAG is a formalism for natural language that employs trees as the basic grammar structures. Parsing involves the application of two operations, called adjunction and substitution, to produce derived tree structures. Sequential parsing algorithms for TAGs run in time quadratic in the grammar size, which is impractical for the very large grammars currently being developed for natural language. This paper presents two parallel algorithms, one running in time nearly linear in the grammar size, and the other running in time logarithmic in the grammar size. Both parallel algorithms were implemented on a Connection Machine CM-2 and performance measurements were obtained for varying grammar sizes.This research was supported in part by NSF Grant BNS-9022010, by the ARO Center for Excellence in Artificial Intelligence, University of Pennsylvania, and by the Army High Performance Computing Research Center (AHPCRC), University of Minnesota.     

Story Parsing Grammar

Story understanding is one of the important branches of natural language understanding research in AI techniques.A new approach to story understanding is proposed in this paper.The so-called Story Parsing Grammar (SPG) is used to represent the story abstracting processes with different degrees in story understanding,and the story understanding process is converted to the storyn recognizing process done by the syntactic parser of SPG.This kind of story understanding is called story parsing.In this paper,firstly,a survey of story understanding research is given.Secondly,by the classification of various kinds of story structures,the so-called Case Frame Forest (CFF) is proposed to represent the superficial meaning of story.Based on CFF,a high-dimen-sional grammar,called Forest Grammar (FG),is defined.Furthermore,SPG is defined as a subclass of context-sensitive FG.Considering the context-sensitivity of story content,a type of context-sensitive derivation is defined in the definition of SPG.Lastly,data about runtime efficiency of the syntactic parsing algorithm of weak precedence SPG,a subclass of SPG,are given and analysed.     

基于GLR算法的新型概率句法分析器

为了提高句法分析器的分歧能力和分析准确率,结合上下文无关概率模型PCFG和头驱动概率模型HDSM各自的优点,提出了一种新型的概率模型PCFG_HDSM,并基于GLR算法,实现了一个新型的汉语句法分析器。在词性标注阶段,通过对助词的详细标注使部分歧义在规则阶段就被去除掉,提高了系统消歧的能力。经过开放测试,准确率和回归率分别达到82.8%、74.7%,与其他分析器分析结果比较有了较大提高,证明新模型PCFG_HDSM确实提高了分析器的分歧能力。     

基于图文法的程序流程图与源代码自动转换

程序流程图在整个软件工程的生命周期中发挥着非常重要的作用。在软件设计中,设计人员通常需要先根据算法从结构上画出程序执行流程图,然后再依据流程图写出相应的源程序代码;在分析和维护软件时,如果能先将源程序代码逆向转换成流程图,则可以有效地帮助分析程序结构。显然,若能让计算机自动地实现流程图与源程序代码之间的相互转换,将大量节省软件开发的人力资源和时间耗费。讨论了如何利用基于边的图文法EGG来自动地实现这种转换,并用具体例子展示了应用EGG图文法的归约和推导操作分别实现流程图的语法分析和流程图的逆向生成,前者可以完成从流程图自动生成源程序代码,而后者则可以从源程序代码自动生成流程图。     

IDS alerts correlation using grammar-based approach

Intrusion Detection System (IDS) is a security technology that attempts to identify intrusions. Defending against multi-step intrusions which prepare for each other is a challenging task. In this paper, we propose a novel approach to alert post-processing and correlation, the Alerts Parser. Different from most other alert correlation methods, our approach treats the alerts as tokens and uses modified version of the LR parser to generate parse trees representing the scenarii in the alerts. An Attribute Context-Free Grammar (ACF-grammar) is used for representing the multi-step attacks. Attack scenarii information and prerequisites/consequences knowledge are included together in the ACF-grammar enhancing the correlation results. The modified LR parser depends on these ACF-grammars to generate parse trees. The experiments were performed on two different sets of network traffic traces, using different open-source and commercial IDS sensors. The discovered scenarii are represented by Correlation Graphs (CGs). The experimental results show that Alerts Parser can work in parallel, effectively correlate related alerts with low false correlation rate, uncover the attack strategies, and generate concise CGs.     

一种基于规则转换的机器翻译方法初探

机器翻译(MachineTranslation,简称MT)是21世纪科技领域的一个难题之一,而要实现机器翻译,对自然语言进行形式化是核心。机器翻译的突破依赖于语言学研究的突破。该文介绍一种汉语句子形式化的方法。涉及的内容包括Montague语法,范畴语法,内涵逻辑,汉语语法等。该文主要在理论上进行了探讨,并用例子进行详细说明该汉语句子形式化方法在英汉机器翻译中的应用。结果表明,该方法具有一定的有效性。     

Resolution of ambiguity in Chinese and its application to machine translation

In this paper, we present a typology of ambiguity in Chinese, which includes morphological, lexical, syntactic, semantic, and contextual ambiguities. Examples are shown for each type of ambiguity and sometimes for subtypes. Ambiguity resolution strategies used in the ALICE machine translation system are presented in various levels of detail. A disambiguation model, called Four-Step, is proposed for resolving syntactic ambiguities involving serial verb construction and predication. As the name suggests, the model comprises four steps-well-formedness checking, preference for argument readings, precondition checking, and late closure. For resolving semantic ambiguity, we propose a new formalism, called Semantic Functional Grammar (SFG), to deal with the resolution problem. SFG integrates the concept of Semantic Grammar into Lexical-Functional Grammar (LFG) such that the functional structure (f-structures) include semantic functions in addition to grammatical functions. For dealing with lexical and contextual ambiguities, we briefly describe the mechanisms used in the ALICE system. As for morphological ambiguity, the resolution is a problem of word-boundary decision (segmentation) and is beyond the scope of this research. The mechanisms presented in the paper have been successfully applied to the translation of Chinese news headlines in the ALICE system.This research was supported partly by the Industrial Technology Research Institute, Taiwan under a grant for doctoral study to this author.     

Weak Precedence Story Parsing Grammar

Story understanding is one of the important branches of natural language understanding research in AI techniques.The story understanding approach based on Story Parsing Grammar (SPG) involves that SPG is used to represent different abstracting processes of stories with different levels in story understanding and that the story understanding process is converted to the recognition process of stories using the syntactic parser of SPG.This kind of story understanding is called story parsing.In this paper,firstly a subclass of SPG,called Weak Precedence SPG(WPSPG),is defined.Afterwards the syntactic parsing algorithm of WPSPG is studied.An example of story parsing is also given.     

基于Earley算法的多功能雷达文法概率快速学习算法

针对基于随机上下文无关文法（SCFG）建模的多功能雷达（MFR）概率学习问题,在传统Inside-Outside（IO）算法和Viterbi-Score（VS）算法的基础上,提出一种基于Earley算法的多功能雷达文法概率快速学习算法。该算法通过对截获的雷达数据进行预处理,构造可以反映派生过程的Earley剖析表,并且基于最大子树概率原则从剖析表中提取出最优剖析树,利用改进的IO算法和改进的VS算法对文法概率进行学习,实现MFR参数估计,得到文法参数后,再利用Viterbi算法对MFR状态进行估计。理论分析和实验仿真表明,与IO算法和VS算法相比,改进算法在保持估计精度的同时,可以有效降低计算复杂度和减少运行时间,验证了Earley算法能够提高文法概率的学习速度。