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

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

AAM反向合成匹配算法及其性能分析

介绍了一种基于反向合成图像对齐算法的AAM匹配算法。首先对反向合成算法的内容及其在AAM匹配过程中需要注意的问题进行了阐述,然后通过实验,分别应用反向合成算法和原始AAM匹配算法对一定数量的图像进行匹配,验证了反向合成算法的有效性。     

非线性微分——代数子系统的逆系统的构造

对于一类非线性微分-代数(Differential-algebraic equation, DAE)子系统, 将非线性常微分方程(Ordinary differential equation, ODE)系统的逆系统方法进行了完全扩展. 首先对此类非线性DAE子系统提出的物理背景和系统特性进行了详细阐述. 然后给出了非线性DAE子系统的逆系统定义, 包括单位右逆系统和 α 阶积分右逆系统. 接下来提出一种递归算法, 利用此算法给出了被控系统可逆的充要条件, 并构造了物理可实现的控制器, 实现了非线性DAE子系统的线性化解耦. 最后基于本文所提出的控制方法, 研究了电力系统同步发电机组励磁汽门综合控制的线性化解耦问题.     

Identification in the limit of categorial grammars

It is proved that for any k, the class of classical categorial grammars that assign at most k types to each symbol in the alphabet is learnable, in the Gold (1967) sense of identification in the limit from positive data. The proof crucially relies on the fact that the concept known as finite elasticity in the inductive inference literature is preserved under the inverse image of a finite-valued relation. The learning algorithm presented here incorporates Buszkowski and Penn's (1990) algorithm for determining categorial grammars from input consisting of functor-argument structures.     

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.     

Matching-Pursuits Dissimilarity Measure for Shape-Based Comparison and Classification of High-Dimensional Data

In this paper, a new matching pursuits dissimilarity measure (MPDM) is presented that compares two signals using the information provided by their matching pursuits (MP) approximations, without requiring any prior domain knowledge. MPDM is a flexible and differentiable measure that can be used to perform shape-based comparisons and fuzzy clustering of very high-dimensional, possibly compressed, data. A novel prototype based classification algorithm, which is termed the computer aided minimization procedure (CAMP), is also proposed. The CAMP algorithm uses the MPDM with the competitive agglomeration (CA) fuzzy clustering algorithm to build reliable shape based prototypes for classification. MP is a well known sparse signal approximation technique, which is commonly used for video and image coding. The dictionary and coefficient information produced by MP has previously been used to define features to build discrimination and prototype based classifiers. However, existing MP based classification applications are quite problem domain specific, thus making their generalization to other problems quite difficult. The proposed CAMP algorithm is the first MP based classification system that requires no assumptions about the problem domain and builds a bridge between the MP and fuzzy clustering algorithms. Experimental results also show that the CAMP algorithm is more resilient to outliers in test data than the multilayer perceptron (MLP) and support-vector-machine (SVM) classifiers, as well as prototype-based classifiers using the Euclidean distance as their dissimilarity measure.     

Parsing of edNLC-graph grammars for scene analysis

An edNLC-graph grammar, introduced by Janssens,⁽⁴⁾ is a strong formalism for generating scene representations. This grammar generates directed node- and edge-labelled graphs, EDG-graphs. A method of construction of unambiguous string EDG-graph representation is briefly described. The characteristics of edNLC-graph grammar for syntactic pattern recognition allows us to construct the parsing algorithm. The deterministic top-down syntax analyzer is constructed for the subfamily of an edNLC-graph grammar, called an ETL/1-graph grammar. An ETL/1-graph grammar is parallel to a finite state string grammar. The notions introduced in the paper are useful for researches in less restricted edNLC-graph grammars, for example grammars analogical to context-free string grammars.     

Defining,analysing and implementing communication protocols using attribute grammars

A new approach to describing communication protocols is introduced. In the style of a formal language, the protocol is considered as the set of all legal sequences of symbols that can be exchanged by the communicating processes. Although context free grammars cannot adequately describe such sequences, it is shown that attribute grammars may be used. Examples are given which show that common protocol features such as interleaving, windowing and flow control can be described by attribute grammars.It is shown how deadlock-proneness of a protocol can be formalised as a property of its attribute grammar specification, and the undecidability of deadlock-proneness for arbitrary grammars is proved. An algorithm is given for determining whether a protocol is deadlock-prone in the decidable case.A method of automatically implementing protocols from their specifications is described. The implementation takes the form of a pair of communicating attributed pushdown automata. These are based on LR(0) parsers, with attribute evaluation being performed in parallel with the parse; attribute values are used to help direct the parse. Consideration is also given to the handling of errors.     

Christiansen Grammar Evolution: Grammatical Evolution With Semantics

This paper describes Christiansen grammar evolution (CGE), a new evolutionary automatic programming algorithm that extends standard grammar evolution (GE) by replacing context-free grammars by Christiansen grammars. GE only takes into account syntactic restrictions to generate valid individuals. CGE adds semantics to ensure that both semantically and syntactically valid individuals are generated. It is empirically shown that our approach improves GE performance and even allows the solution of some problems are difficult to tackle by GE     

Evolutionary induction of stochastic context free grammars

This paper describes an evolutionary approach to the problem of inferring stochastic context-free grammars from finite language samples. The approach employs a distributed, steady-state genetic algorithm, with a fitness function incorporating a prior over the space of possible grammars. Our choice of prior is designed to bias learning towards structurally simpler grammars. Solutions to the inference problem are evolved by optimizing the parameters of a covering grammar for a given language sample. Full details are given of our genetic algorithm (GA) and of our fitness function for grammars. We present the results of a number of experiments in learning grammars for a range of formal languages. Finally we compare the grammars induced using the GA-based approach with those found using the inside-outside algorithm. We find that our approach learns grammars that are both compact and fit the corpus data well.     

Learning deterministic context free grammars: The Omphalos competition

This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages. Editor: Georgios Paliouras and Yasubumi Sakakibara     

Multilevel projection algorithm for solving obstacle problems

Obstacle problems are nonlinear free boundary problems and the computation of approximate solutions can be difficult and expensive. Little work has been done on effective numerical methods of such problems. This paper addresses some aspects of this issue. Discretizing the problem in a continuous piecewise linear finite element space gives a quadratic programming problem with inequality constraints. A new method, called the multilevel projection (MP) method, is established in this paper. The MP algorithm extends the multigrid method for linear equations to nonlinear obstacle problems. The convergence theorems of this method are also proved. A numerical example presented shows our error estimate is sharp and the MP algorithm is robust.     

Fast recognition of context-sensitive structures

This paper is concerned with an extension of context-free LL(k) grammars, called RLL(k) grammars. RLL(k) grammars are powerful enough to generate non-context-free languages. In particular context-sensitive constructs of programming languages can be formalized conveniently. RLL(k) grammars have the pleasant property that fast syntactical check procedures exist. An algorithm for syntactical analysis with linear average cost is developed in this paper. A worst case quadratic upper bound is derived.     

Efficient monitoring of parametric context-free patterns

Recent developments in runtime verification and monitoring show that parametric regular and temporal logic specifications can be efficiently monitored against large programs. However, these logics reduce to ordinary finite automata, limiting their expressivity. For example, neither can specify structured properties that refer to the call stack of the program. While context-free grammars (CFGs) are expressive and well-understood, existing techniques for monitoring CFGs generate large runtime overhead in real-life applications. This paper demonstrates that monitoring parametric CFGs is practical (with overhead on the order of 12% or lower in most cases). We present a monitor synthesis algorithm for CFGs based on an LR(1) parsing algorithm, modified to account for good prefix matching. In addition, a logic-independent mechanism is introduced to support matching against the suffixes of execution traces.     

BP-MPSO混合算法在机器人空间路径中的应用

在对PUMA机器人空间路径进行BP算法环境建模与目标建模的基础上,针对传统粒子群优化（PSO）算法搜索空间有限、容易陷入局部最优点的缺陷,提出了一种改进的粒子群优化（MPSO）算法。该算法引入了基于全局信息反馈的重新初始化过程机制,并对PUMA机器人空间路径进行了优化。仿真实验表明,该算法的应用不仅降低了求解逆运动方程的难度,还能得到全局最优解。显著地提高了PUMA机器人空间路径优化的效率。     

Actor grammars

Actor systems are a model of massively parallel systems based on asynchronous message passing. This paper presents a formalism for a restricted version of actor systems in the framework of graph grammars. To this aim actor grammars are introduced, motivated, and illustrated by examples. Some of the basic properties pertinent to graph transformations in actor grammars are discussed.     

Grammar constraints

With the introduction of the Regular Membership Constraint, a new line of research has opened where constraints are based on formal languages. This paper is taking the next step, namely to investigate constraints based on grammars higher up in the Chomsky hierarchy. We devise a time- and space-efficient incremental arc-consistency algorithm for context-free grammars, investigate when logic combinations of grammar constraints are tractable, show how to exploit non-constant size grammars and reorderings of languages, and study where the boundaries run between regular, context-free, and context-sensitive grammar filtering.     

A unifying approach to picture grammars

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using an approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling, named regional, and define the corresponding regional tile grammars. They include both Siromoney?s (or Matz?s) Kolam grammars and their generalization by Pr?ša, as well as Drewes?s grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).     

A direct algorithm for checking equivalence of LL(k) grammars

We deal with the problem of testing equivalence of two LL(k) grammars. The problem had been shown to be decidable for general k by Rosenkrantz and Stearns [2], who solved it by reduction into an equivalence problem for special DPDA's. In a paper by Korenjak and Hopcroft [1] the equivalence problem for LL(1) grammars is solved by a branching algorithm operating directly on the grammars. Our work presents a direct branching algorithm for the general LL(k) grammars equivalence problem.     

Search-based inference of dialect grammars

Building parsers is an essential task for the development of many tools, from software maintenance tools to any kind of business-specific, programmable environment having a command-line interface. Whilst grammars for many programming languages are available, these are, very often, almost useless because of the large diffusion of dialects and variants not contemplated by standard grammars. Writing a grammar by hand is clearly feasible, however it can be a tedious and error-prone task, requiring appropriate skills not always available. Grammar inference is a possible, challenging approach for obtaining suitable grammars from program examples. However, inference from scratch poses serious scalability issues and tends to produce correct, but meaningless grammars, hard to be understood and used to build tools. This paper describes an approach, based on genetic algorithms, for evolving existing grammars towards target (dialect) grammars, inferring changes from examples written using the dialect. Results obtained experimenting the inference of C dialect rules show that the algorithm is able to successfully evolve the grammar. Inspections indicated that the changes automatically made to the grammar during its evolution preserved its meaningfulness, and were comparable to what a developer could have done by hand.