Finding Syntactic Structures from Human Motion Data

We present a new approach to motion rearrangement that preserves the syntactic structures of an input motion automatically by learning a context‐free grammar from the motion data. For grammatical analysis, we reduce an input motion into a string of terminal symbols by segmenting the motion into a series of subsequences, and then associating a group of similar subsequences with the same symbol. To obtain the most repetitive and precise set of terminals, we search for an optimial segmentation such that a large number of subsequences can be clustered into groups with little error. Once the input motion has been encoded as a string, a grammar induction algorithm is employed to build up a context‐free grammar so that the grammar can reconstruct the original string accurately as well as generate novel strings sharing their syntactic structures with the original string. Given any new strings from the learned grammar, it is straightforward to synthesize motion sequences by replacing each terminal symbol with its associated motion segment, and stitching every motion segment sequentially. We demonstrate the usefulness and flexibility of our approach by learning grammars from a large diversity of human motions, and reproducing their syntactic structures in new motion sequences.     

Neural networks discover a near-identity relation to distinguish simple syntactic forms

Computer simulations show that an unstructured neural-network model [Shultz, T. R., & Bale, A. C. (2001). Infancy, 2, 501–536] covers the essential features␣of infant learning of simple grammars in an artificial language [Marcus, G. F., Vijayan, S., Bandi Rao, S., & Vishton, P. M. (1999). Science, 283, 77–80], and generalizes to examples both outside and inside of the range of training sentences. Knowledge-representation analyses confirm that these networks discover that duplicate words in the sentences are nearly identical and that they use this near-identity relation to distinguish sentences that are consistent or inconsistent with a familiar grammar. Recent simulations that were claimed to show that this model did not really learn these grammars [Vilcu, M., & Hadley, R. F. (2005). Minds and Machines, 15, 359–382] confounded syntactic types with speech sounds and did not perform standard statistical tests of results.     

Parsing Arabic using induced probabilistic context free grammar

The importance of the parsing task for NLP applications is well understood. However developing parsers remains difficult because of the complexity of the Arabic language. Most parsers are based on syntactic grammars that describe the syntactic structures of a language. The development of these grammars is laborious and time consuming. In this paper we present our method for building an Arabic parser based on an induced grammar, PCFG grammar. We first induce the PCFG grammar from an Arabic Treebank. Then, we implement the parser that assigns syntactic structure to each input sentence. The parser is tested on sentences extracted from the treebank (1650 sentences).We calculate the precision, recall and f-measure. Our experimental results showed the efficiency of the proposed parser for parsing modern standard Arabic sentences (Precision: 83.59 %, Recall: 82.98 % and F-measure: 83.23 %).     

Compact coding of syntax tables

A method for constructing compact syntax tables in three steps is presented. First, the rules of a grammar are mapped into a syntax graph, from which five syntactic forms are defined. Secondly, the grammar expressed in these syntactic forms is mapped into data structures. Finally, from the data structures, the compact syntax table of the grammar is constructed.     

Syntactic complexity of context-free grammars over word monoids

 The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems are formulated. Received October 10, 1994/February 23, 1995     

基于句式结构的汉语图解析句法设计

梳理了汉语语法学界对“句式”这一术语的认识分歧;从中文信息处理角度分析了当前本领域句法分析和树库构建缺乏句式结构的现状;对黎氏语法形式化研究作了一个最新的综述,指出其在句式结构方面的优势和仍存在的不足;以黎氏语法图解法为原型改造设计出一种新型的汉语图解析句法,具体包括图形化的句法结构表示和结构化的XML存储格式。     

A graph grammar-based formal validation of object-process diagrams

Two basic requirements from a system’s conceptual model are correctness and comprehensibility. Most modeling methodologies satisfy only one of these apparently contradicting requirements, usually comprehensibility, leaving aside problems of correctness and ambiguousness that are associated with expressiveness. Some formal modeling languages do exist, but in these languages a complete model of a complex system is fairly complicated to understand. Object-process methodology (OPM) is a holistic systems modeling methodology that combines the two major aspects of a system—structure and behavior—in one model, providing mechanisms to manage the complexity of the model using refinement-abstraction operations, which divide a complex system into many interconnected diagrams. Although the basic syntax and semantics of an OPM model are defined, they are incomplete and leave room for incorrect or ambiguous models. This work advances the formal definition of OPM by providing a graph grammar for creating and checking OPM diagrams. The grammar provides a validation methodology of the semantic and syntactic correctness of a single object-process diagram.     

A Mathematical Model of Prediction-Driven Instability: How Social Structure Can Drive Language Change

I discuss a stochastic model of language learning and change. During a syntactic change, each speaker makes use of constructions from two different idealized grammars at variable rates. The model incorporates regularization in that speakers have a slight preference for using the dominant idealized grammar. It also includes incrementation: The population is divided into two interacting generations. Children can detect correlations between age and speech. They then predict where the population’s language is moving and speak according to that prediction, which represents a social force encouraging children not to sound out-dated. Both regularization and incrementation turn out to be necessary for spontaneous language change to occur on a reasonable time scale and run to completion monotonically. Chance correlation between age and speech may be amplified by these social forces, eventually leading to a syntactic change through prediction-driven instability.     

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.     

基于《知网》信息结构模式的词汇化树邻接文法消歧

针对词汇化树邻接法的歧义现象,利用《知网-信息结构库》作为知识库,并引入概率方法提出了一种有效的句法树消歧方法。中阐述了如何利用知网信息结构模式对句法树进行筛选,并提出了基于概率的信息结构抽取的计算方法。     

Grammar Induction by Unification of Type-logical Lexicons

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees. Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log Lang Inf 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary.     

模式识别的一类属性文法

本文叙述了在通常的文法中引入两个基元间连接属性的重要性,从而看出在属性文法 中,句法和词意两部分间可以有折衷的关系,即增加后者的复杂性将会使前者得到简化,反之 亦然,这样使便于应用的有限状态属性文法成为基本的形式.这里作者吸取了PDL,Plex Grammar,Tree Grammar中连接关系的优点,引入连接属性,提出一类关联属性文法.这类 文法可以有效地描述和识别曲线段构成的图形,如汉字、电子线路图等.     

Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars.     

Thermodynamic database for analysis of the process of obtaining silicate building materials from natural raw material

A thermodynamic database is described that is oriented toward the analysis of chemical reactions, chemical compounds, and processes of production of silicate building materials. Its distinctive feature is the representation of chemical compounds and reactions in the form of string data with their subsequent syntactic analysis and automatic determination of the composition and masses of products of chemical reactions, taking into account the distinctive features of the representation of a composition of materials used in production engineering of building materials. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 183–188, January–February 2007.     

A predictive bottom-up parser

Despite all advances in parsing, parser size, conflict resolution and error recovery are still of important consideration. In this research, we propose a predictive bottom-up parser. The parser is implemented in two versions. Both versions constitute an algorithm that simulates the run of a shift–reduce automaton, defined and constructed in a way that integrates its parsing actions with reduction prediction, conflict resolution and error recovery. However, the first implementation version performs explicit shift–reduce parsing actions based on implicit prediction of the reduction sequences. The second one performs parsing actions based on explicit prediction of the reduction sequences with implied shift–reduce actions. The proposed parser has been experimented against the ones based on similar approaches. 10–20% reduction of the parser size has been achieved, with a parsing behaviour proportional to a factor reflecting the grammar ambiguity.     

汉语句子的组块分析体系

介绍了一种描述能力介于线性词序列和完整句法树表示之间的浅层句法知识描述体系－组块分析体系,并详细讨论了其中两大部分;词界块和成分组的基本内容及其自动识别算法,在此基础上,提出了一种分阶段构造汉语树库的新设想,即先构造组块库,再构造树库,进行了一系列句法分析和知识获取实验,包括１）自然识别汉语最长名词短语;２）自动获取汉语句法知识等。所有这些工作都证明了这种知识描述体系的实用性和有效性。     

A Generative System for Mamluk Madrasa Form-Making

In this paper, a parametric shape grammar for the derivation of the floor plans of educational buildings (madrasas) in Mamluk architecture is presented. The grammar is constructed using a corpus of sixteen Mamluk madrasas that were built in Egypt, Syria, and Palestine during the Mamluk period. Based on an epistemological premise of structuralism, the morphology of Mamluk madrasas is analyzed to deduce commonalities of the formal and compositional aspects among them. The set of underlying common lexical and syntactic elements that are shared by the study cases is listed. The shape rule schemata to derive Mamluk madrasa floor plans are formulated. The sets of lexical elements and syntactic rules are systematized to form a linguistic framework. The theoretical framework for the formal language of Mamluk architecture is structured to establish a basis for a computerized model for the automatic derivation of Mamluk madrasa floor plans.