Tile rewriting grammars and picture languages

Tile rewriting grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into an isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to context-free grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the tiling systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context-free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals.     

Parameter reduction and automata evaluation for grammar-compressed trees

Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.     

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.     

A CKY parser for picture grammars

We study the complexity of the membership or parsing problem for pictures generated by a family of picture grammars: Siromoney's Context-Free Kolam Array grammars (coincident with Matz's context-free picture grammars). We describe a new parsing algorithm, which extends the Cocke, Kasami and Younger's classical parsing technique for string languages and preserves the polynomial time complexity.     

Spinal-Formed Context-Free Tree Grammars

In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce acceptors called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks. Received May 29, 1998, and in revised form April 27, 1999, and in final form May 10, 1999.     

Linearity and nondeletion on monadic context-free tree grammars

In this paper, subclasses of monadic context-free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs generate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and nondeletion on monadic CFTGs are necessary to generate the same class of languages.     

A NEW AUTOMATON MODEL FOR TAGS: 2-SA

In this paper, we introduce and define a new class of automata (pushdown automata with n stacks, abbreviated as n-SA). The ultimate aim is to give a new characterization of LCRFL, the class of languages accepted by a linear context-free rewriting system (LCFRS). In particular, we introduce 2-SA as a new automaton model for tree-adjoining grammars (TAG). In the simplest cases (0-SA and 1-SA), the languages that are accepted by the automata are the regular and context-free languages respectively. A more complex case is the case of a 2-SA which accepts TALs. The n-SA creates an infinite hierarchy of languages and it seems that this hierarchy corresponds to others in the class LCFRL. The 2-SA corresponds closely to the EPDA (embedded pushdown automaton, an automaton model equivalent to TAGs). Unlike the EPDA, which allows push operations "below the top stack," an n-SA allows push and pop operations only on the top of their (multiple) stacks. So n-SA trade simpler operations against an also simpler but expanded storage structure.     

Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

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.     

Context-free like restrictions on selective rewriting

Selective substitution grammars based on ‘context-free’ productions form a possible framework for the study of ‘grammatically oriented’ formal language theory. Such grammars (with no control governing the composition of derivation steps) are studied in this paper. In particular we study the effect of various conditions on selectors (which define the way that rewriting is performed); those conditions are aimed to formalize the notion of ‘using information about the context’ during the rewriting process. Each of them captures a particular feature of a rewriting according to a context-free grammar or an EOS system (essentially a context-free grammar that can also rewrite terminal symbols). Some of those conditions yield characterizations of the class of context-free languages for other conditions the lower and upper bound on the language generating power are given. Also a natural notion of a class of ‘simple’ rewriting systems is introduced (pattern grammars) and it is demonstrated that they possess surprisingly high language generating power.     

The complexity of the membership problem for some extensions of context-free languagest†

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.     

The complexity of graph languages generated by hyperedge replacement

Summary Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.Parts of the results of this paper were presented at 15^th ICALP, [La88b]     

A characterization of context-free string languages by directed node-label controlled graph grammars

Summary Directed node-label controlled graph grammars (DNLC grammars) are sequential graph rewriting systems. In a direct derivation step of a DNLC grammar a single node is rewritten. Both the rewriting of a node and the embedding of a daughter graph in a host graph are controlled by the labels of nodes only. We study the use of those grammars to define string languages. In particular we provide a characterization of the class of context-free string languages in terms of DNLC grammars.     

The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the two-dimensional yield of an MSO-definable three-dimensional tree language.     

Simple restriction in context-free rewriting

Many rewriting systems with context-free productions and with controlled derivations have been studied. On one hand, these systems preserve the simplicity of applications of context-free productions and, on the other hand, they increase the generative power to cover more aspects of natural and programming languages. However, with λ-productions, many of these systems are computationally complete. It gives rise to a natural question of what are the simplest restrictions of the derivation process of context-free grammars to obtain the universal power. In this paper, we present such a simple restriction introducing so-called restricted context-free rewriting systems. These systems are context-free grammars with a function assigning a nonterminal coupled with + or − to each nonterminal. A production is applicable if it is applicable as a context-free production and if the symbol assigned to the left-hand side of the production is coupled with +, then this symbol has to appear in the sentential form, while if coupled with −, it must not appear in the sentential form. This restriction is simpler than most of the other restrictions, since the context conditions are assigned to nonterminals, not to productions, and their type is the simplest possible – a nonterminal.     

Two collapsing hierarchies of subregularly tree controlled languages

Tree controlled grammars are context-free grammars where the associated language only contains those terminal words which have a derivation where the word of any level of the corresponding derivation tree belongs to a given regular language. In this paper, we consider first as control sets such regular languages which can be represented by finite unions of monoids. We show that the corresponding hierarchy of tree controlled languages collapses already at the second level. Second, we restrict the number of states allowed in the accepting automaton of the regular control language. We prove that the associated hierarchy has at most five levels.     

Learning context-free grammars using tabular representations

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.     

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.     

On the synchronized derivation depth of context-free grammars

We consider depth of derivations as a complexity measure for synchronized and ordinary context-free grammars. This measure differs from the earlier considered synchronization depth in that it counts the depth of the entire derivation tree. We consider (non-)existence of trade-offs when using synchronized grammars as opposed to non-synchronized grammars and establish lower bounds for certain classes of linear context-free languages.