On the ontological expressiveness of information systems analysis and design grammars

Abstract. Information systems analysis and design (ISAD) methodologies provide facilities for describing existing or conceived real-world systems. These facilities are ontologically expressive if they are capable of describing all real-world phenomena completely and clearly. In this paper we formally examine the notion of the ontological expressiveness of a grammar and discuss some of its implications for the design and use of ISAD methodologies. We identify some generic ways in which ontological expressiveness may be undermined in a grammar and some potential consequences of these violations. We also examine ontological expressiveness within the context of some other desirable features that might be considered in the design of ISAD methodologies.     

Silver: an Extensible Attribute Grammar System

Attribute grammar specification languages, like many domain specific languages, offer significant advantages to their users, such as high-level declarative constructs and domain-specific analyses. Despite these advantages, attribute grammars are often not adopted to the degree that their proponents envision. One practical obstacle to their adoption is a perceived lack of both domain-specific and general purpose language features needed to address the many different aspects of a problem. Here we describe Silver, an extensible attribute grammar specification language, and show how it can be extended with general purpose features such as pattern matching and domain specific features such as collection attributes and constructs for supporting data-flow analysis of imperative programs. The result is an attribute grammar specification language with a rich set of language features. Silver is implemented in itself by a Silver attribute grammar and utilizes forwarding to implement the extensions in a cost-effective manner.     

Silver: An extensible attribute grammar system

Attribute grammar specification languages, like many domain-specific languages, offer significant advantages to their users, such as high-level declarative constructs and domain-specific analyses. Despite these advantages, attribute grammars are often not adopted to the degree that their proponents envision. One practical obstacle to their adoption is a perceived lack of both domain-specific and general purpose language features needed to address the many different aspects of a problem. Here we describe Silver, an extensible attribute grammar specification system, and show how it can be extended with general purpose features such as pattern matching and domain-specific features such as collection attributes and constructs for supporting data-flow analysis of imperative programs. The result is an attribute grammar specification language with a rich set of language features. Silver is implemented in itself by a Silver attribute grammar and utilizes forwarding to implement the extensions in a cost-effective manner.     

The covering problem for linear context-free grammars

Language equivalence, grammatical covering and structural equivalence are all notions of similarity defined on context-free grammars. We show that the problem of determining whether an arbitrary linear context-free grammar covers another is complete for the class of languages accepted by polynomially space bounded Turing machines. We then compare the complexity of this problem with the analogous problems for language equivalence and structural equivalence, not only for linear grammars, but also for regular grammars and unrestricted context-free grammars. As a step in obtaining the main result of this paper, we show that the equivalence problem for linear s-grammars is decidable in polynomial time.     

Toward a formal research framework for ontological analyses

Ontological analyses have been used in numerous publications to compare existing modelling grammars with an ontology. However, a sound theoretical research framework is still missing. Consequently, working with the results of such ontological analyses is theoretically questionable. Therefore, the aim of this paper is threefold. Firstly, we want to contribute to such a theoretical research framework by formalising the ontological analyses approach as sets of mathematical functions between ontological and modelling grammar constructs. Secondly, on this basis, we derive four formal requirements each ontological analyses must comply with. Thirdly, we analyse whether current state of the art ontological analyses comply with our findings. While the formalisation demonstrates the strengths of the ontological analysis approach we conclude that current analyses have theoretical deficiencies, which lead to serious limitations in their application. Lastly, we demonstrate the usefulness of our formal framework by describing a new application. This application uses two different ontological analyses as input and produces mappings between the modelling grammars used in these analyses as output.     

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.     

Analyzing ambiguity of context-free grammars

It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this by presenting an ambiguity analysis framework based on conservative language approximations. As a concrete example, we propose a technique based on local regular approximations and grammar unfoldings. We evaluate the analysis using grammars that occur in RNA analysis in bioinformatics, and we demonstrate that it is sufficiently precise and efficient to be practically useful.     

一个上下文无关文法的构造定理及其在推断中的应用

递归概念可以在句子中重复派生、循环出现。对这样的句子推断时,若为递归概念的每一个派生部分引进一个递归概念来描述,将推断出多个与之有相似的产生式结构的递归概念,同时也构造出一个新文法。本文先给出新文法的形式化构造方法,证明了新文法与原文法的等价性。在文章的后部,通过实例,介绍该定理在简化复杂文法推断中的应用。     

Graph grammars with string-regulated rewriting

Multicellular organisms undergo a complex developmental process, orchestrated by the genetic information in their cells, in order to form a newborn individual from a fertilized egg. This complex process, not completely understood yet, is believed to have a key role in generating the impressive biotic diversity of organisms found on earth. Inspired by mechanisms of Eukaryotic genetic expression, we propose and analyse graph grammars with string-regulated rewriting. In these grammatical systems a genome sequence is represented by a regulatory string, a graph corresponds to an organism, and a set of graph grammar rules represents different forms of implementing cell division. Accordingly, a graph derivation by the graph grammar resembles the developmental process of an organism. We give examples of the concept and compare its generative power to the power of the traditional context-free graph grammars. We demonstrate that the power of expression increases when genetic regulation is included in the model, as compared to non-regulated grammars. Additionally, we propose a hierarchy of string-regulated graph grammars, arranged by expressive power. These results highlight the key role that the transmission of regulatory information during development has in the emergence of biological diversity.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

Grammars++ for modelling information in text

Grammars provide a convenient means to describe the set of valid instances in a text database. Flexibility in choosing a grammar can be exploited to provide information modelling capability by designing productions in the grammar to represent entities and relationships of interest to database applications. Additional constraints can be specified by attaching predicates to selected nonterminals in the grammar. When used for database definition, grammars can provide the functionality that users have come to expect of database schemas. Extended grammars can also be used to specify database manipulation, including query, update, view definition, and index specification.     

Graph grammars for evolutionary 3D design

A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are presented, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is more rich in organised designs. A set of numerical features are defined over designs. They are shown to be effective in distinguishing between the designs produced by the two representations, and between designs labelled by users as good or bad. The features allow the definition of a non-interactive fitness function in terms of proximity to target feature vectors. In non-interactive experiments with this fitness function, the graph grammar representation out-performs the alternative graph representation, and evolution out-performs random search.     

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.     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

Evolving encapsulated programs as shared grammars

Facilitating the discovery and reuse of modular building blocks is generally regarded as the key to achieving better scalability in genetic programming (GP). A precedent for this exists in biology, where complex designs are the product of developmental processes that can also be abstractly modeled as generative grammars. We introduce shared grammar evolution (SGE), which aligns grammatical development with the common application of grammars in GP as a means of establishing declarative bias. Programs are derived from and represented by a global context-free grammar that is transformed and extended according to another, user-defined grammar. Grammatical productions and the subroutines they encapsulate are shared between programs, which enables their reuse without reevaluation and can significantly reduce total evaluation time for large programs and populations. Several variants of SGE employing different strategies for controlling solution size and diversity are tested on classic GP problems. Results compare favorably against GP and newer techniques, with the best results obtained by promoting diversity between derived programs.     

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

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

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.