THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context-free grammars, multiple context-free grammars, and their subclasses are discussed.     

Finding the smallest binarization of a CFG is NP-hard

Grammar binarization is the process and result of transforming a grammar to an equivalent form whose rules contain at most two symbols in their right-hand side. Binarization is used, explicitly or implicity, by a wide range of parsers for context-free grammars and other grammatical formalisms. Non-trivial grammars can be binarized in multiple ways, but in order to optimize the parser's computational cost, it is convenient to choose a binarization that is as small as possible. While several authors have explored heuristics to obtain compact binarizations, none of them guarantee that the resulting grammar has minimum size. However, to our knowledge, no hardness results for this problem have been published. In this article, we address this issue and prove that the problem of finding a minimum binarization of a given context-free grammar is NP-hard, by reduction from vertex cover. We also provide a lower bound on the approximability of this problem.     

Parsing nonlinear languages

The diagrammatic approach to user interfaces for computer-aided software development toolkits, visual query systems, and visual programming environments, is based on the use of diagrams and charts traditionally drawn on paper. In particular, the VLG system (Visual Language Generator) has been proposed to generate icon-oriented visual languages customized for given applications. The syntactical model underlying the interpretation of a visual language in VLG has been designed to describe icon-oriented visual languages. In order to enable the VLG system to apply to any kind of graphical languages, like diagrammatic ones, it is necessary to find a more general syntactical model able to support both their generation and interpretation. This paper addresses the comprehension of the features that a grammatical formalism for nonlinear languages must have to match any requirement for an efficient parsing. To this aim, relation grammars support an easy implementation of a general parsing algorithm for multidimensional languages, parametric with respect to the rewriting rules of the grammar. We compare the expressive power of relation grammars to grammatical formalisms for graph grammars     

Dynamic interpretations of constraint-based grammar formalisms

We present a rendering of some common grammatical formalisms in terms of evolving algebras. Though our main concern in this paper is on constraint-based formalisms, we also discuss the more basic case of context-free grammars. Our aim throughout is to highlight the use of evolving algebras as a specification tool to obtain grammar formalisms.     

The equivalence of four extensions of context-free grammars

There is currently considerable interest among computational linguists in grammatical formalisms with highly restricted generative power. This paper concerns the relationship between the class of string languages generated by several such formalisms, namely, combinatory categorial grammars, head grammars, linear indexed grammars, and tree adjoining grammars. Each of these formalisms is known to generate a larger class of languages than context-free grammars. The four formalisms under consideration were developed independently and appear superficially to be quite different from one another. The result presented in this paper is that all four of the formalisms under consideration generate exactly the same class of string languages.This work has been supported by NSF Grants MCS-82-19116-CER, MCS-82-07294, DCR-84-10413, IRI-8909810, ARO Grant DAA29-84-9-0027, and DARPA Grant N0014-85-K0018.     

Meta-modelling and graph grammars for multi-paradigm modelling in AToM<Superscript>3</Superscript>

This paper presents the combined use of meta-modelling and graph grammars for the generation of visual modelling tools for simulation formalisms. In meta-modelling, formalisms are described at a meta-level. This information is used by a meta-model processor to generate modelling tools for the described formalisms. We combine meta-modelling with graph grammars to extend the model manipulation capabilities of the generated modelling tools: edit, simulate, transform into another formalism, optimize and generate code. We store all (meta-)models as graphs, and thus, express model manipulations as graph grammars.We present the design and implementation of these concepts in AToM³ (A_To_ol for M_ulti-formalism, M_eta-M_odelling). AToM³ supports modelling of complex systems using different formalisms, all meta-modelled in their own right. Models in different formalisms may be transformed into a single common formalism for further processing. These transformations are specified by graph grammars. Mosterman and Vangheluwe [18] introduced the term multi-paradigm modelling to denote the combination of multiple formalisms, multiple abstraction levels, and meta-modelling. As an example of multi-paradigm modelling we present a meta-model for the Object-Oriented Continuous Simulation Language OOCSMP, in which we combine ideas from UML class diagrams (to express the OOCSMP model structure), Causal Block Diagrams (CBDs), and Statecharts (to specify the methods of the OOCSMP classes). A graph grammar is able to generate OOCSMP code, and then a compiler for this language (C-OOL) generates Java applets for the simulation execution.     

从短语到构式: 构式知识库建设的若干理论问题探析

构式语法(construction grammar)在汉语语法学界已引起持续关注,但在自然语言处理领域,将构式语法理论应用到计算机自动句法语义分析中的研究还很少见。该文提出构建现代汉语构式知识库的语言工程任务,讨论了构式与传统语法单位的关系、构式的形式表示、构式的内部小类及主要特征等。     

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.     

Toward a lexicalized grammar for interlinguas

In this paper we present one aspect of our research on machine translation (MT): capturing the grammatical and computational relation between (i) the interlingua (IL) as defined declaratively in the lexicon and (ii) the IL as defined procedurally by way of algorithms that compose and decompose pivot IL forms. We begin by examining the interlinguas in the lexicons of a variety of current IL-based approaches to MT. This brief survey makes it clear that no consensus exists among MT researchers on the level of representation for defining the IL. In the section that follows, we explore the consequences of this missing formal framework for MT system builders who develop their own lexical-IL entries. The lack of software tools to support rapid IL respecification and testing greatly hampers their ability to modify representations to handle new data and new domains. Our view is that IL-based MT research needs both (a) the formal framework to specify possible IL grammars and (b) the software support tools to implement and test these grammars. With respect to (a), we propose adopting a lexicalized grammar approach, tapping research results from the study oftree grammars for natural language syntax. With respect to (b), we sketch the design and functional specifications for parts of ILustrate, the set of software tools that we need to implement and test the various IL formalisms that meet the requirements of a lexicalized grammar. In this way, we begin to address a basic issue in MT research, how to define and test an interlingua as a computational language — without building a full MT system for each possible IL formalism that might be proposed.     

vCGG:一种基于虚结点的空间图文法形式框架

作为一种二维的形式化方法,图文法为可视化语言提供了直观而规范的描述手段.然而,大多数图文法形式框架在空间语义处理能力方面有所不足,影响了图文法的表达能力及其实际应用范围.针对现存的问题,构建了一种新型空间图文法形式框架vCGG （virtual-node based coordinate graph grammar）.区别于其他空间图文法,vCGG在产生式中通过定义虚结点的概念描述产生式与主图之间的语法结构与空间语义关系,在保留抽象能力的同时,提高了其空间语义配置性能.通过与几种典型空间图文法框架比较,vCGG形式框架在直观性、规范性、表达能力以及分析效率方面均有着较好的表现.     

班智达藏文语料切分词典的建立与算法研究

随着自然语言信息处理的不断发展和完善,大规模语料文本处理已经成为计算语言学界的一个热门话题。一个重要的原因是从大规模的语料库中能够提取出所需要的知识。而语料文本的处理与加工以语法信息词典作基础。结合藏文语料库切分标注规范,论述了对藏文语料库切分与标注用的藏文语法信息词典的建立和设计,重点讨论了该词典的内容建设、语法信息的标注、索引结构及查找算法。     

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.     

Describing morphological phenomena of modern greek using a unification grammar formalism

The unification-based formalism, suitable for encoding a wide variety of grammars for computational applications and the linguistic research, can also be applied to the area of computational morphology. The morphological processor, presented in this paper, is based on the PATR II formalism and provides the system with a context-sensitive approach as opposed to the more classical finite state automaton approach. It has been designed as a tool to describe a range of linguistic models, in which unification plays the centrol role. Our software system can be used to describe various morphological phenomena of Modern Greek (and any other highly inflected language) such as inflection, derivation, accentuation, composition, etc. Stored morphological information representing a word, is operationally divided into syntactic and semantic parts and is described in terms of attribute-value pairs. The unification-based formalism provides a unified approach to deal with the stratified levels of linguistic information, namely morphology, syntax and semantics.     

Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

A wide range of parser generators are used to generate parsers for programming languages. The grammar formalisms that come with parser generators provide different approaches for defining operator precedence. Some generators (e.g. YACC) support precedence declarations, others require the grammar to be unambiguous, thus encoding the precedence rules. Even if the grammar formalism provides precedence rules, a particular grammar might not use it. The result is grammar variants implementing the same language. For the C language, the GNU Compiler uses YACC with precedence rules, the C-Transformers uses SDF without priorities, while the SDF library does use priorities. For PHP, Zend uses YACC with precedence rules, whereas PHP-front uses SDF with priority and associativity declarations.The variance between grammars raises the question if the precedence rules of one grammar are compatible with those of another. This is usually not obvious, since some languages have complex precedence rules. Also, for some parser generators the semantics of precedence rules is defined operationally, which makes it hard to reason about their effect on the defined language. We present a method and tool for comparing the precedence rules of different grammars and parser generators. Although it is undecidable whether two grammars define the same language, this tool provides support for comparing and recovering precedence rules, which is especially useful for reliable migration of a grammar from one grammar formalism to another. We evaluate our method by the application to non-trivial mainstream programming languages, such as PHP and C.     

Expression of syntactic and semantic features in logic-based grammars

In this paper, we introduce and initiate a formalism to represent syntactic and semantic features in logic-based grammars. We also introduce technical devices to express feature-checking and feature-inheritance mechanisms. This leads us to propose some extensions to the basic unification mechanism of PROLOG. Finally, we consider the problem of long-distance dependency relations between constituents in gapping grammars rules from the point of view of morphosyntactic features that may change depending on the position occupied by the moved constituents. What we propose is not a new linguistic theory about features, but rather a formalism and a set of tools that we think will be useful to grammar writers to describe features and their relations in grammar rules.     

可视化语言技术在软件开发中的应用

可视化语言技术比一维文本语言在描述软件组成方面具有优越性.由于图表和图形概念在系统建模中的广泛使用,可视化语言可以应用于需求分析、设计、测试和维护等软件开发的各个阶段.除了具有直观易见的特点之外,图文法在计算机上的精确建模和验证能力,为设计可视化语言提供了一个坚实的理论基础.讨论了可视化语言的形式理论基础,回顾了相关的可视化图形编程环境.特别提出了一种空间图文法,并且用该图文法定义了统一建模语言的行为语义.基于空间图文法,开发了一种基于模式驱动的框架,以帮助软件架构与设计.     

A survey of grammatical inference in software engineering

Grammatical inference – used successfully in a variety of fields such as pattern recognition, computational biology and natural language processing – is the process of automatically inferring a grammar by examining the sentences of an unknown language. Software engineering can also benefit from grammatical inference. Unlike these other fields, which use grammars as a convenient tool to model naturally occurring patterns, software engineering treats grammars as first-class objects typically created and maintained for a specific purpose by human designers. We introduce the theory of grammatical inference and review the state of the art as it relates to software engineering.     

Using Meta-Modelling and Graph Grammars to Create Modelling Environments

This paper presents the combined use of meta-modelling and graph grammars for the generation of visual modelling tools for simulation formalisms. In meta-modelling, formalisms are described at a meta-level. This information is used by a meta-model processor to generate modelling tools for the described formalisms. We combine meta-modelling with graph grammars to extend the model manipulation capabilities of the generated modelling tools, as we store (meta-)models as graphs, and thus, express model manipulations as graph grammars.We show the design and implementation of these concepts in AToM³ (A Tool for Multi-formalism, Meta-Modelling). As an example we will present a meta-model for Causal Block Diagrams and a graph grammar to generate OOCSMP code, a continuous simulation language which has a compiler able to generate Java applets from the simulations models.