逐步求精法获取上下文无关文法

文法推断研究如何从语言的有限实例,通过归纳推断获取语言的文法定义。文中提出一个基于逐步求精的上下文无关文法推断方法,以尝试将文法推断用于替代或帮助传统手工的文法构造工作。文中的推断方法以Ａｎｇｌｕｉｎｈ的交互式学习模型为框架,以逐步求精和复用为主要策略,具有增量式获取结构自然的文法的特点。     

可交换上下文无关文法

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

上下文无关文法推断中的几条启发规则及其应用

本文先简要介绍了一种上下文无关文法的推断方法--逐步求精法,然后论述了递归概念在文法推断中的核心作用,并从递归概念的特殊性质出发提出了多条启发规则,能有效减少无效探求和与用户交互的次数,尤其适合于文法较复杂、例句集信息量较大的情况。这些启发规则同时也适用于对上下文无关文法的其它推断方法。     

一个上下文无关文法获取过程的设计和实现*

文章介绍一个基于复用的上下文无关文法获取过程的设计和实现,该过程用于获取以上下文无关文法表示的概念.它从待获取概念的有限实例和句型以及可能复用的已知概念出发,通过一个交互式文法推断过程,最终得到概念的文法定义.     

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

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

一种有效的结点标号上下文无关图文法分析算法

本文讨论了上下文无关图文法的性质,并证明了图文法推导具有独立性．本文还给出了一种有效的上下文无关图文法分析算法,它具有多项式时间复杂性,并给出了算法的正确性证明．该算法已经用Ｃ语言实现．     

基于上下文无关文法的仿真类层次结构模型1

本文分析了分布式交互仿真系统中仿真类体系结构的特点,提出一种基于上下文无关文法的仿真类体系的形式化定义方法,并讨论了仿真类树的精炼以及仿真类的组合运算。     

基于上下文无关文法的可逆变换模型

可逆变换和双向变换等数据转换问题一直是近年来的研究热点,研究人员针对该问题提出了大量相关的语言和模型。但是,这些实现往往建立在一种新的计算模型上,从而导致需要花费较大的学习成本去了解计算模型。另一方面,作为语法解析的基本工具,上下文无关文法对于绝大多数程序员来说都是不陌生的。提出了一种基于上下文无关文法的计算模型,用来构造字符串上的可逆变换,并对其性质和表达能力进行了探讨。采用Scheme语言实现了该计算模型,并通过在MIPS指令集上进行汇编和反汇编开发验证了该模型。验证结果表明,该模型具有较强的表达能力,在添加小型的公共数值变换模块后,可以完整地实现MIPS指令集上的汇编和反汇编。     

含有某种限制的上下文无关文法之LR分析

本文给出一种扩充LR分析方法以使其能够处理含有嵌套限制的上下文无关文法之办法。在基于LR的分析程序中，通常要借助执行LR方法的上下文以外的语义代码处理这样的限制，由于LR方法本身就含有这样的限制，所以潜在的移动归纳与归约归约的冲突可被解决并能进一步制约认可的语言，推荐的方法很蝗于并入现有的基于LR的分析程序生成系统。     

基于概率上下文无关文法的句法分析歧义消解新模式

基于自然语言句法歧义消解常用的一种概率模型-概率上下文无关文法,融入上下文相关的概率信息,提出一种新的歧义消解计算模式,该模式经测试可以有效地提高句法分析中歧义消解的正确率。     

A Version Space Approach to Learning Context-free Grammars

In principle, the version space approach can be applied to any induction problem. However, in some cases the representation language for generalizations is so powerful that (1) some of the update functions for the version space are not effectively computable, and (2) the version space contains infinitely many generalizations. The class of context-free grammars is a simple representation that exhibits these problems. This paper presents an algorithm that solves both problems for this domain. Given a sequence of strings, the algorithm incrementally constructs a data structure that has nearly all the beneficial properties of a version space. The algorithm is fast enough to solve small induction problems completely, and it serves as a framework for biases that permit the solution of larger problems heuristically. The same basic approach may be applied to representations that include context-free grammars as special cases, such as And-Or graphs, production systems, and Horn clauses.     

Stochastic Grammatical Inference of Text Database Structure

For a document collection in which structural elements are identified with markup, it is often necessary to construct a grammar retrospectively that constrains element nesting and ordering. This has been addressed by others as an application of grammatical inference. We describe an approach based on stochastic grammatical inference which scales more naturally to large data sets and produces models with richer semantics. We adopt an algorithm that produces stochastic finite automata and describe modifications that enable better interactive control of results. Our experimental evaluation uses four document collections with varying structure.     

Characteristic Sets for Polynomial Grammatical Inference

When concerned about efficient grammatical inference two issues are relevant: the first one is to determine the quality of the result, and the second is to try to use polynomial time and space. A typical idea to deal with the first point is to say that an algorithm performs well if it infers in the limit the correct language. The second point has led to debate about how to define polynomial time: the main definitions of polynomial inference have been proposed by Pitt and Angluin. We return in this paper to a definition proposed by Gold that requires a characteristic set of strings to exist for each grammar, and this set to be polynomial in the size of the grammar or automaton that is to be learned, where the size of the sample is the sum of the lengths of all strings it includes. The learning algorithm must also infer correctly as soon as the characteristic set is included in the data. We first show that this definition corresponds to a notion of teachability as defined by Goldman and Mathias. By adapting their teacher/learner model to grammatical inference we prove that languages given by context-free grammars, simple deterministic grammars, linear grammars and nondeterministic finite automata are not identifiable in the limit from polynomial time and data.     

Inference of a class of CFPG by means of semantic rules

An important property of Context-Free Programmed Grammars (CFPG) is that some context-sensitive Languages can be generated by CFPG. To infer a special class of CFPG for syntactic pattern recognition is the motivation of this paper. First an one-dimensional string is transformed into a corresponding binary tree. Then in terms of the structure of subtrees, and the semantic rules corresponding to the context-free productions, a method for the inference of Context-free Programmed Grammar is presented. Inference of Stochastic Context-Free Programmed Grammar (STCFPG) by the maximum-likelihood estimate approach is also discussed.This work was supported in part by the NSF Grant ECS 78-16970.     

Noisy Time Series Prediction using Recurrent Neural Networks and Grammatical Inference

Financial forecasting is an example of a signal processing problem which is challenging due to small sample sizes, high noise, non-stationarity, and non-linearity. Neural networks have been very successful in a number of signal processing applications. We discuss fundamental limitations and inherent difficulties when using neural networks for the processing of high noise, small sample size signals. We introduce a new intelligent signal processing method which addresses the difficulties. The method proposed uses conversion into a symbolic representation with a self-organizing map, and grammatical inference with recurrent neural networks. We apply the method to the prediction of daily foreign exchange rates, addressing difficulties with non-stationarity, overfitting, and unequal a priori class probabilities, and we find significant predictability in comprehensive experiments covering 5 different foreign exchange rates. The method correctly predicts the directionof change for the next day with an error rate of 47.1%. The error rate reduces to around 40% when rejecting examples where the system has low confidence in its prediction. We show that the symbolic representation aids the extraction of symbolic knowledge from the trained recurrent neural networks in the form of deterministic finite state automata. These automata explain the operation of the system and are often relatively simple. Automata rules related to well known behavior such as tr end following and mean reversal are extracted.     

Stochastic Inference of Regular Tree Languages

We generalize a former algorithm for regular language identification from stochastic samples to the case of tree languages. It can also be used to identify context-free languages when structural information about the strings is available. The procedure identifies equivalent subtrees in the sample and outputs the hypothesis in linear time with the number of examples. The results are evaluated with a method that computes efficiently the relative entropy between the target grammar and the inferred one.     

面向推理构件分布式应用环境的构建

以知识系统为背景，采用多agent技术构造了面向推理构件的分布式计算环境，提出了一种支持推理构件协同问题求解的解决方案，并设计了此分布式应用的关键部件，从而实现了推理构件求解问题时知识查询和协同推理的双重功能，知识系统的可用性得以提高．     

Inference by generating in deductive databases

A method, APEX, for query evaluation in deductive databases presented in this work is based on discovering of axioms and facts relevant to a given query. The notion of relevancy and migration of facts is derived from an analysis of data flow in the system. APEX is complete, and incorporates efficient query evaluation heuristics. Operation of APEX is illustrated by sample databases involving non-linear recursive axioms and cyclic relations. Main virtues of the method are its generality and adaptivity: it imposes no restrictions on the structure of axioms or the contents of relations, and it employs the knowledge of the actual data acquired at each step of a query evaluation.     

Mathematical Fundamentals of Constructing Fuzzy Bayesian Inference Techniques

Problems and an associated technique for developing a Bayesian approach to decision-making in the case of fuzzy data are presented. The concept of fuzzy and pseudofuzzy quantities is introduced and main operations with pseudofuzzy quantities are considered. The basic relationships and the principal concepts of the Bayesian decision procedure based on the modus-ponens rule are proposed. Some problems concerned with the practical realization of the fuzzy Bayesian method are considered.