Resolution of ambiguity in parsing

Summary The use of context-free grammars to define the syntax of programming languages is complicated by the phenomenon of ambiguity. Ambiguity can be resolved by the specification of a unique canonical parse. A set of rules is given which defines a canonical bottom-up parse, and these rules are implemented in a left-to-right bottom-up parsing algorithm. A second set of rules is given which defines a canonical top-down parse, and these rules are similarly implemented in a left-to-right top-down parsing algorithm.     

A stochastic graph grammar for compositional object representation and recognition

This paper illustrates a hierarchical generative model for representing and recognizing compositional object categories with large intra-category variance. In this model, objects are broken into their constituent parts and the variability of configurations and relationships between these parts are modeled by stochastic attribute graph grammars, which are embedded in an And-Or graph for each compositional object category. It combines the power of a stochastic context free grammar (SCFG) to express the variability of part configurations, and a Markov random field (MRF) to represent the pictorial spatial relationships between these parts. As a generative model, different object instances of a category can be realized as a traversal through the And-Or graph to arrive at a valid configuration (like a valid sentence in language, by analogy). The inference/recognition procedure is intimately tied to the structure of the model and follows a probabilistic formulation consisting of bottom-up detection steps for the parts, which in turn recursively activate the grammar rules for top-down verification and searches for missing parts. We present experiments comparing our results to state of art methods and demonstrate the potential of our proposed framework on compositional objects with cluttered backgrounds using training and testing data from the public Lotus Hill and Caltech datasets.     

Mining Layered Grammar Rules for Action Recognition

We propose a layered-grammar model to represent actions. Using this model, an action is represented by a set of grammar rules. The bottom layer of an action instance’s parse tree contains action primitives such as spatiotemporal (ST) interest points. At each layer above, we iteratively mine grammar rules and “super rules” that account for the high-order compositional feature structures. The grammar rules are categorized into three classes according to three different ST-relations of their action components, namely the strong relation, weak relation and stochastic relation. These ST-relations characterize different action styles (degree of stiffness), and they are pursued in terms of grammar rules for the purpose of action recognition. By adopting the Emerging Pattern (EP) mining algorithm for relation pursuit, the learned production rules are statistically significant and discriminative. Using the learned rules, the parse tree of an action video is constructed by combining a bottom-up rule detection step and a top-down ambiguous rule pruning step. An action instance is recognized based on the discriminative configurations generated by the production rules of its parse tree. Experiments confirm that by incorporating the high-order feature statistics, the proposed method largely improves the recognition performance over the bag-of-words models.     

EGG图文法语法分析算法的研究

EGG是一种基于边的上下文相关图文法形式化框架,其语法分析(归约操作)算法是该文法重要的组成部分。在简要介绍EGG的基础上,给出了EGG语法分析算法的设计,其中包括子图匹配算法、子图替换算法和算法计算复杂性的分析。为了展示如何用EGG来定义图语言,特别是如何用所设计的归约算法来分析图,文中以程序流程图为例,给出了相关的EGG形式定义以及对一个具体流程图的归约过程,并探讨了可能降低分析算法复杂性的一些途径。     

基于图和双向搜索的频繁项集挖掘算法

基于图的关联规则挖掘算法会产生大量候选项集。针对该问题,提出一种结合双向搜索策略的改进算法。按照支持度对频繁 1-项集排序,对频繁k-项集的最长超集进行验证,利用Apriori算法进行剪枝。实验结果表明,在支持度阈值较小时,改进算法能有效减少候选项集的数量,提高挖掘效率。     

Parsing with restricted quantification: an initial demonstration1

The primary goal of this paper is to illustrate how smaller deductive search spaces can be obtained by extending a logical language with restricted quantification and tailoring an inference system to this extension. The illustration examines the search spaces for a bottom-up parse of a sentence with a series of four strongly equivalent grammars. The grammars are stated in logical languages of increasing expressiveness, each restatement resulting in a more concise grammar and a smaller search space. A secondary goal is to point out an area where further research could yield results useful to the design of efficient parsers, particularly for grammatical formalisms that rely heavily on feature systems.     

基于SCNF和概率CYK算法的最佳剖析树

对基于纯规则(chart)的自底向上方法进行句法剖析后出现的大量无法消解的歧义现象,通过引入概率型Chomsky范式(SCNF)在一定程度上消除部分句法结构歧义;在利用Inside-Outside算法进行参数自动训练,并通过语法示例验证Inside-Outside算法的收敛性后,最后采用概率CYK算法得到句子的最佳剖析树.     

Definite-clause set grammars: a formalism for problem solving

First, we present definite-clause set grammars (DCSG), a DCG-like formalism for free-word-order languages. The DCSG formalism is well suited for problem solving. By dealing with DCSG as a generalized parsing problem, we avoid a certain type of looping problem in backward chaining. Next, we extend DCSG by viewing grammar rules as definitions for set conversions. In order to realize inverse conversions, we introduce an inverse operator into DCSG syntax. This operator enables partial bottom-up analyses in the DCSG top-down parsing process. Next, we discuss a looping problem called “left recursion” in top-down parsing. The looping problem is avoided by the bottom-up mechanism of the extended DCSG. The bottom-up mechanism can be viewed as the top-down controlled firing of production rules. Unlike most production systems, production systems written in extended DCSG can backtrack and produce alternative solutions. DCSG is a simple but powerful tool for generalized parsing problems which involve finding structures in a given data set.     

Parsing electronic circuits in a logic grammar

Understanding circuits is a prerequisite for circuit design and trouble shooting. Circuit understanding by engineers is described as a process that starts with a structural analysis and then proceeds to a causal analysis. As a step toward automatic circuit understanding, a method for analyzing circuit structures is presented. In this method, a circuit is reviewed as a sentence and its elements as words. Circuit structures are defined by rules written in a logic grammar called definite clause set grammar (DCSG). Given circuits are decomposed into parse trees by the DCSG top-down parsing mechanism. These parse trees represent hierarchical structures of functional blocks. This representation is presented as one step in the process of automatic understanding of circuit structures     

Deterministic grammars and grammar morphisms

Summary The present categorial approach to bottom-up parsing context free grammars treats two aspects of determinism. One is an abstraction of grammatical determinism from actual parsing strategies. The other is the transfer of determinism under grammar transformations. The approach is based on the characterization of a parse step as categorial limit, which on the one hand yields a convenient pattern for grammar type definition, and leads on the other hand in a transparent way to invariance results on deterministic grammars under homomorphic transformations.     

A class of linearly parsable graph grammars

Summary Specializing an existing graph grammar model we look in detail at node context-free graph grammars. With a slight generalization the parse trees for context-free Chomsky grammars can be used to describe derivations of these graph grammars.As shown already in former works the precedence graph grammars are defined as a subclass of context-free graph grammars by certain algebraic restrictions on the form of the rules. Then we can prove that every precedence grammar is unambiguous and additionally the reduction process in such a grammar read as replacement system is finite.The most important aim in defining the predence relations was a simple parsing method. This is realized because it is shown that the syntactic analysis for precedence graph grammars can be done in a time which linearly depends on the size of the input graph.The whole method has been implemented and a documentation is available.     

Problem reduction representation for the linguistic analysis of waveforms

This paper shows how the nondirectional structural analysis of pattern data can be performed by matching a problem reduction representation (PRR) of pattern structure with sample data, using a best-first state space search algorithm called SSS*. The end result of the matching algorithm is a tree whose nodes represent recognized structures in the data. Tip nodes of the tree structure correspond to primitives which are recognized in the raw data by curve fitting routines. The operators of the algorithm allow the tree to be constructed with a combination of top-down or bottom-up steps. The matching of the structure tree to waveform segments need not be done in a left-right sequence. Moreover ambiguous matches are pursued in a best first order by using state space search with partial parse trees as states. A software system called WAPSYS (for waveform parsing system) is described, which implements this structural analysis paradigm. Experience using WAPSYS to analyze carotid pulse waves is also discussed.     

上下文相关图文法的表达能力分析

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

Digital media adoption in schools: Bottom-up,top-down,complementary or optional?

Past research has suggested that innovation processes in schools are more successful when they are participatory and voluntary. To examine this notion, we categorized schools into one of four different innovation-process types, based on group interviews with school staff: complementary bottom-up and top-down development (type 1), top-down development that is not supported bottom-up (type 2), bottom-up development that is not supported top-down (type 3) and optional development with neither strong bottom-up nor top-down initiatives (type 4). Based on this typology, analysis of variance was then conducted on survey response data from 357 teachers and 1051 9th grade students from these schools. In contrast with some of our expectations, we found that teachers in schools with a complementary top-down and bottom-up strategy as well as schools with a top-down strategy only showed better ICT-resources and a more intensive use of educational technology than those in bottom-up- or optional-innovation-type schools. Additionally, teachers' ICT-use in type 1 and 2 schools is predicted to a higher degree by the number of computers in the classroom than in schools where ICT-integration is bottom-up or optional. Our findings suggest that bottom-up innovation strategies are likely to fall short without top-down support, especially when funds for technology installations are missing.     

Parsing Ill-Formed Text Using an Error Grammar

This paper presents a robust parsing approach which is designed to address the issue of syntactic errors in text. The approach is based on the concept of an error grammar which is a grammar of ungrammatical sentences. An error grammar is derived from a conventional grammar on the basis of an analysis of a corpus of observed ill-formed sentences. A robust parsing algorithm is presented which is applied after a conventional bottom–up parsing algorithm has failed. This algorithm combines a rule from the error grammar with rules from the normal grammar to arrive at a parse for an ungrammatical sentence. This algorithm is applied to 50 test sentences, with encouraging results.     

Algorithms for search trees on message passing architectures

In this paper we describe a new algorithm for maintaining a balanced search tree on a message-passing MIMD architecture; the algorithm is particularly well suited for implementation on a small number of processors. We introduce a (2^B-2, 2^B) search tree that uses a bidirectional ring of O(log n) processors to store n entries. Update operations use a bottom-up node-splitting scheme, which performs significantly better than top-down search tree algorithms. The bottom-up algorithm requires many fewer messages and results in less blocking due to synchronization than top-down algorithms. Additionally, for a given cost ratio of computation to communication the value of B may be varied to maximize performance. Implementations on a parallel-architecture simulator are described     

Image Parsing: Unifying Segmentation,Detection, and Recognition

In this paper we present a Bayesian framework for parsing images into their constituent visual patterns. The parsing algorithm optimizes the posterior probability and outputs a scene representation as a parsing graph, in a spirit similar to parsing sentences in speech and natural language. The algorithm constructs the parsing graph and re-configures it dynamically using a set of moves, which are mostly reversible Markov chain jumps. This computational framework integrates two popular inference approaches—generative (top-down) methods and discriminative (bottom-up) methods. The former formulates the posterior probability in terms of generative models for images defined by likelihood functions and priors. The latter computes discriminative probabilities based on a sequence (cascade) of bottom-up tests/filters. In our Markov chain algorithm design, the posterior probability, defined by the generative models, is the invariant (target) probability for the Markov chain, and the discriminative probabilities are used to construct proposal probabilities to drive the Markov chain. Intuitively, the bottom-up discriminative probabilities activate top-down generative models. In this paper, we focus on two types of visual patterns—generic visual patterns, such as texture and shading, and object patterns including human faces and text. These types of patterns compete and cooperate to explain the image and so image parsing unifies image segmentation, object detection, and recognition (if we use generic visual patterns only then image parsing will correspond to image segmentation (Tu and Zhu, 2002. IEEE Trans. PAMI, 24(5):657–673). We illustrate our algorithm on natural images of complex city scenes and show examples where image segmentation can be improved by allowing object specific knowledge to disambiguate low-level segmentation cues, and conversely where object detection can be improved by using generic visual patterns to explain away shadows and occlusions.     

基于延迟合并嵌入的带障碍的时钟树布线算法

提出一种在带障碍情况下,基于延迟合并嵌入方法的时钟树构建算法,并在时钟树构造过程中引入了轨迹图以保证布线可以绕过障碍．该算法以已知障碍为布线约束,首先自底向上计算时钟树内部节点的可能位置,然后自顶向下确定每个节点的确切位置．实验结果表明,该算法能够正确、有效地实现有障碍存在时的时钟树布线,线长优化率超过7％．     

Execution time analysis of a top-down R-tree construction algorithm

A detailed CPU execution-time analysis and implementation are given for a bulk loading algorithm to construct R-trees due to García et al. [Y.J. García, M.A. López, S.T. Leutenegger, A greedy algorithm for bulk loading R-trees, in: GIS'98: Proc. of the 6th ACM Intl. Symp. on Advances in Geographic Information Systems, Washington, DC, 1998, pp. 163-164] which is known as the top-down greedy split (TGS) bulk loading algorithm. The TGS algorithm makes use of a classical bottom-up packing approach. In addition, an alternative packing approach termed top-down packing is introduced which may lead to improved query performance, and it is shown how to incorporate it into the TGS algorithm. A discussion is also presented of the tradeoffs of using the bottom-up and top-down packing approaches.     

A visual attention model for robot object tracking

Inspired by human behaviors, a robot object tracking model is proposed on the basis of visual attention mechanism, which is fit for the theory of topological perception. The model integrates the image-driven, bottom-up attention and the object-driven, top-down attention, whereas the previous attention model has mostly focused on either the bottom-up or top-down attention. By the bottom-up component, the whole scene is segmented into the ground region and the salient regions. Guided by top-down strategy which is achieved by a topological graph, the object regions are separated from the salient regions. The salient regions except the object regions are the barrier regions. In order to estimate the model, a mobile robot platform is developed, on which some experiments are implemented. The experimental results indicate that processing an image with a resolution of 752*480 pixels takes less than 200ms and the object regions are unabridged. The analysis obtained by comparing the proposed model with the existing model demonstrates that the proposed model has some advantages in robot object tracking in terms of speed and efficiency.