Search

Grammars with contexts are an extension of context-free grammars equipped with operators for referring to the left and the right contexts of a substring being defined. These grammars are notable for still having a cubic-time parsing algorithm, as well as for being able to describe some useful syntactic constructs, such as declaration before use. It is proved in this paper that every language described by a grammar with contexts can be recognized in deterministic linear space.

We consider d-dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d≥2, d-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages.

We present theoretical foundations, and a practical implementation, that makes the method of Algebraic Dynamic Programming available for Multiple Context-Free Grammars. This allows to formulate optimization problems, where the search space can be described by such grammars, in a concise manner and solutions may be obtained efficiently. This improves on the previous state of the art which required complex code based on hand-written dynamic programming recursions. We apply our method to the RNA pseudoknotted secondary structure prediction problem from computational biology.Appendix and supporting files available at: http://www.bioinf.uni-leipzig.de/Software/gADP/

In a recent paper (M. Barash, A. Okhotin, "An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O ( n 4 ) , where n is the length of the input string.

The paper introduces node replacement graph grammars with dynamic node relabeling as an extension of the eNCE families of graph grammars. Initiated by NLC grammars in which graph embedding is based on node labels only, node distinction of the embedded graph extended NLC grammars to NCE grammars and dynamic edge relabeling further extended NCE grammars to eNCE grammars. Now, dynamic node relabeling, the node counterpart of the dynamic edge relabeling, is introduced as the next extension, which we call neNCE. The paper analyzes basic language-theoretical properties of the neNCE system.

Categorial Dependency Grammars (CDGs) are classical categorial grammars extended by oriented polarized valencies. At the same time, CDGs represent a class of completely lexicalized dependency grammars. They express both projective and non-projective dependencies. CDGs generate non-context-free languages. At that, they are parsed in polynomial time under realistic conditions. CDGs possess a normal form that is analogous to Greibach normal form for cf-grammars. CDG-languages are closed under almost all AFL operations and are accepted by a special class of push-down automata with independent counters.

The well-known parsing algorithm for context-free grammars due to Valiant (1975) [25] is analyzed and extended to handle the more general Boolean grammars, which are context-free grammars augmented with conjunction and negation operators in the rules. The algorithm reduces construction of a parsing table to computing multiple products of Boolean matrices of various sizes. Its time complexity on an input string of length n is O(BMM(n)logn), where BMM(n) is the number of operations needed to multiply two Boolean matrices of size nxn, which is O(n^@w) with @w

This paper deals with regulated grammars. Specifically, it studies one-sided random context grammars. It demonstrates that any recursively enumerable language can be generated by these grammars with no more than two right random context rules.

A tree controlled grammar is specified as a pair (G,G′) where G is a context-free grammar and G′ is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree–except the last level–belong to L(G′). We define the nonterminal complexity V ar(H) of H=(G,G′) as the sum of the numbers of nonterminals of G and G′. In Turaev et al. (2011) [23] it is shown that tree controlled grammars H with V ar(H)≤9 are sufficient to generate all recursively enumerable languages. In this paper, we improve the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a nonterminal complexity bounded by three, and we prove that this bound is optimal for the mentioned language families. Furthermore, we show that any context-free language can be generated by a tree controlled grammar (G,G′) where the number of nonterminals of G and G′ is at most four.

The paper studies the family of Boolean LL languages, generated by Boolean grammars and usable with the recursive descent parsing. It is demonstrated that over a one-letter alphabet, these languages are always regular, while Boolean LL subsets of Σ ∗ a ∗ obey a certain periodicity property, which, in particular, makes the language { a n b 2 n | n ⩾ 0 } non-representable. It is also shown that linear conjunctive LL grammars cannot generate any language of the form L ⋅ { a , b } , with L non-regular, and that no languages of the form L ⋅ c ∗ , with non-regular L , can be generated by any linear Boolean LL grammars. These results are used to establish a detailed hierarchy and closure properties of these and related families of formal languages.

This paper establishes a workspace theorem in terms of regular-controlled (context-free) grammars. It proves that, if, for a regular-controlled grammar H, there is a positive integer k such that H generates every sentence [email protected]?L(H) by a derivation in which every sentential form x contains at most (k-1)|x|/k occurrences of nonterminals that are erased throughout the rest of the derivation, where |x| denotes the length of x, then the language of H is generated by a propagating regular-controlled grammar. An analogical workspace theorem is demonstrated for regular-controlled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regular-controlled grammar (possibly with appearance checking) that satisfies the workspace condition above without affecting the generated language. In its conclusion, the paper points out a relationship of the workspace theorems to other areas of formal language theory.

We obtain a simple, purely game-theoretic characterization of Boolean grammars [A. Okhotin, Boolean grammars, Information and Computation, 194(1) (2004) 19-481. In particular, we propose a two-player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and offers a promising new connection between game theory and formal languages. (C) 2010 Elsevier B.V. All rights reserved. Theoretical Computer Science

Motivated by applications that require mechanisms for describing the structure of object-oriented programs, adaptive star grammars are introduced, and their fundamental properties are studied. In adaptive star grammars, rules are actually schemata which, via the cloning of so-called multiple nodes, may adapt to potentially infinitely many contexts when they are applied. This mechanism makes adaptive star grammars more powerful than context-free graph grammars. Nevertheless, they turn out to be restricted enough to share some of the basic characteristics of context-free devices. In particular, the underlying substitution operator enjoys associativity and confluence properties quite similar to those of context-free graph grammars, and the membership problem for adaptive star grammars is decidable.

It is shown that every conjunctive language is generated by a conjunctive grammar from a special subclass, in which every nonterminal A has at most one rule of the general form A->@a"[email protected]"n, while the rest of the rules for A must be of the type A->w, where w is a terminal string. For context-free grammars, a similar property does not hold (S.A. Greibach et al. (1992) [3]). If it is furthermore required that each rule A->w has a nonempty w, then a substantial subfamily of conjunctive languages can be generated, yet it remains unknown whether such grammars are as powerful as conjunctive grammars of the general form.

The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.

Leftist grammars were introduced by Motwani et al., who established the relationship between the complexity of the accessibility problem (or safety problem) for certain general protection systems and the membership problem for these grammars. The membership problem for leftist grammars is decidable. This implies the decidability of the accessibility problem. It is shown that the membership problem for leftist grammars is PSPACE-hard. Therefore, the accessibility problem in the appropriate protection systems is PSPACE-hard as well. Furthermore, the PSPACE-hardness result is adapted to a very restricted class of leftist grammars, if the grammar is a part of the input.

The t-contextual grammars are generalizations of Marcus contextual grammars, which insert t contexts in each derivation step. If the selection mappings are regular and satisfy an additional locality restriction, then these grammars correspond in their expressive power to restarting automata with cut-index t. In the first part of the paper classes of languages are studied that are accepted by certain types of restarting automata with limited cut-index. As already R-automata with cut-index 1 accept NP-complete languages, additional restrictions in the form of certain monotonicity conditions are also considered. Without the locality restriction t-contextual grammars with regular selection correspond to t-RR-automata with cut-index one. These are RR-automata that are allowed to perform up to t deletion operations in each cycle that each delete a single factor only. In the second part of the paper the expressive power of these automata is studied, where the focus is on the special case that certain monotonicity conditions are satisfied.

An enhanced generative formalism is proposed based on the combination of two features: contextual derivation (as in Marcus contextual grammars) and sorted dependency structures (as in dependency grammars). The model is related to a variant of restarting automaton with rewriting and deletion. Preliminary results on the generative power as well as closure and decidability properties of the new model are presented.

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.

State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75–85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated.

In this paper we make a comparison between two methods for the enumeration of combinatorial objects, namely the ECO method and object grammars, both based on a recursive description for the examined class of objects. In particular, we study the problem of passing from an object grammar to an “equivalent” ECO system. First, we solve this problem for any unidimensional, unambiguous, and complete object grammar, with any linear parameter. Then we treat the more complex cases of q-linear parameters, and of multidimensional object grammars, giving some explanatory examples. In particular, we determine a new ECO system for the class of directed convex polyominoes.

Constructive methods for obtaining regular grammar counterparts for some sub-classes of context-free grammars (CFGs) have been investigated by many researchers. An important class of grammars for which this is always possible is the one-letter CFG. We show in this paper a new constructive method for transforming an arbitrary one-letter CFG to an equivalent regular expression of star-height 0 or 1. Our new result is considerably simpler than a previous construction by Leiss, and we also propose a new normal form for a regular expression with only a single-star occurrence. Through an alphabet factorization theorem, we show how to go beyond the one-letter CFG in a straight-forward way.

The present paper introduces and discusses forbidding ET0L grammars whose productions have some attached strings, called forbidding conditions. These grammars can make a derivation step only by using productions whose forbidding conditions do not appear in the rewritten sentential form. The paper demonstrates that some well-known relationships concerning the language families resulting from ordinary ET0L grammars do not hold in terms of the forbidding ET0L grammars. Most interestingly, while E0L grammars are less powerful than ET0L grammars, their forbidding versions with conditions of length one are equally powerful. On the other hand, while EP0L grammars are as powerful as E0L grammars, FEP0L grammars are less powerful than FE0L grammars.

Conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. This paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations.The algorithm is in fact an extension of the context-free recognition and parsing algorithm due to Graham, Harrison and Ruzzo, and it retains the cubic time complexity of its prototype. It is shown that for the case of linear conjunctive grammars this algorithm can be modified to work in quadratic time and use linear space.The given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's P-completeness, as well as P-completeness of the membership problem for linear conjunctive grammars.

We use random context picture grammers to generate pictures through successive refinement. The productions of such a grammar are context free, but their application is regulated by context randomly distributed in the developing picture. Grammars using this relatively weak context often succeed where context-free grammars fail, e.g., in generating the typical iteration sequence of the Sierpiński carpet. On the other hand, it proved possible to develop iteration theorems for three subclasses of these grammars; finding necessary conditions is problematic in the case of most models of context-free picture grammars with context-sensing ability, since they consider a variable and its context as a connected unit.We present a property of all picture sets generated with random context picture grammers, and then construct a picture set that does not belong to this class.

A new systematic approach for the specification of bijections between sets of combinatorial objects is presented. It is based on the notion of object grammars. Object grammars give recursive descriptions of objects and generalize context-free grammars. The study of a particular substitution in these object grammars confirms once more the key role of Dyck words in the domain of enumerative and bijective combinatorics.

Earley's parsing algorithm is shown to be an abstract interpretation of a refinement of the derivation semantics of context-free grammars.

Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin ("An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014) further extending the author's earlier work on propositional connectives in grammars (A. Okhotin, "Conjunctive grammars", J. Autom. Lang. Comb., 2001). These grammars allow two types of context specifications: for a substring v of a string uvx, a proper left context operator ?D states that u is of the form described by D, and an extended left context operator ?E states that uv is described by E. This paper establishes a normal form for these grammars, in which extended left contexts are never used, whereas left contexts may be applied only to individual symbols, so that all rules are of the form A ? B 1 C 1 & ? & B m C m or A ? a & ? D . This eliminates circular dependencies in the grammar and leads to a new, clearer version of the known cubic-time parsing algorithm. With some further improvements, the algorithm is accelerated from time O ( n 3 ) to time O ( n 3 log ? n ) .

This paper discusses the descriptional complexity of scattered context grammars with respect to the number of nonterminals. It proves that the three-nonterminal scattered context grammars characterize the family of recursively enumerable languages.

We introduce a hypergraph-generating system, called HRNCE grammars, which is structurally simple and descriptively powerful. An HRNCE grammar replaces a handle (i.e., a hyperedge together with its incident nodes) by a hypergraph, whose nodes are connected to (or contained in) the hyperedges surrounding the replaced handle by using the eNCE rewriting mechanism. HRNCE grammars can generate all recursively enumerable languages. HRNCE grammars without edge erasing can generate PSPACE-complete languages. Separated HRNCE (S-HRNCE) grammars have many useful normal forms, including Chomsky, Greibach, and context-free normal forms. S-HRNCE languages are in NP and there is an NP-complete linear HRNCE (Lin-HRNCE) language satisfying any two of the following conditions: connected; degree-bounded; and rankbounded. On the other hand, S-HRNCE (Lin-HRNCE) languages satisfying all these three conditions are in LOGCFL (NLOG) and there is such a language which is LOGCFL-complete (NLOG-complete). The equivalence problem is undecidable for Lin-HRNCE languages.

In this note, we bring to evidence some techniques that can be performed on PC grammar systems working with linear grammars. This allows us to show that the generative power of (centralized) PC grammar systems working with right-linear grammars is bigger than expected, and to prove closure properties of the families of languages generated by centralized PC grammar systems working with (right-)linear grammars, such as the closure under union and the closure under intersection with a rational set, and for centralized PC grammar systems working with right-linear grammars, the closure under product.

Context-free grammars are used in several algebraic specification formalisms instead of first-order signatures for the definition of the structure of algebras, because grammars provide better notation than signatures. The rigidity of these first-order structures enforces a choice between strongly typed structures with little genericity or generic operations over untyped structures. In two-level signatures level 1 defines the algebra of types used at level 0 providing the possibility to define polymorphic abstract data types. Two-level grammars are the grammatical counterpart of two-level signatures. This paper discusses the correspondence between context-free grammars and first-order signatures, the extension of this correspondence to two-level grammars and signatures, examples of the usage of two-level grammars for polymorphic syntax definition, a restriction of the class of two-level grammars for which the parsing problem is decidable, a parsing algorithm that yields a minimal and finite set of most general parse trees for this class of grammars, and a proof of its correctness.

We consider the following restriction of internal contextual grammars, called local: in any derivation in a grammar, after applying a context, further contexts can be added only inside of or at most adjacent to the previous ones. We further consider a natural restriction of this derivation mode by requiring that no superword of the word considered as selector can be used as selector. We investigate the relevance of the latter type of grammars for natural language study. In this aim, we show that all the three basic non-context-free constructions in natural languages, that is, multiple agreements, crossed agreements, and duplication, can be realized using this type of grammars. Our main result is that these languages are parsable in polynomial time. The problem of semilinearity remains open.

This article presents an overview of a framework called categorial grammars from a theoretical and algorithmic perspective. It provides an introduction to the formalisms of these grammars and of the tools they use (the Lambek Calculus) for theoretical computer scientists who are not familiar with them. We give a clear presentation of the main classical and recent results on these grammars, especially those concerning their links with context-free grammars.The purpose is also to use these results so as to efficiently solve the membership problem with categorial grammars. We compare the complexity of the algorithms for this problem deduced from the initial formulation of the categorial grammars and the one obtained by translating these grammars into context-free formalism and by applying the Cocke-Kasami-Younger algorithm. We show that a polynomial algorithm is always available.

This paper defines a geometric hierarchy of language classes the first member of which is context-free languages. This hierarchy generalizes the difference between context-free languages and the class of languages generated by four weakly equivalent grammar formalisms that are of interest to computational linguists. A grammatical characterization of the hierarchy is given using a variant of control grammars. Each member of the progression is shown to share many of the attractive features of context-free grammars, in particular, we show that each member is an abstract family of languages. We give a progression of automata and show that it corresponds exactly to the language hierarchy defined with control grammars.

Control grammars, a generalization of context-free grammars recently introduced for use in natural language recognition, are investigated. In particular, it is shown that a hierarchy of non-context-free languages, called control language hierarchy (CLH), generated by control grammars can be recognized in polynomial time. Previously, the best-known upper bound was exponential time. It is also shown that CLH is in NC(2), the class of languages recognizable by uniform boolean circuits of polynomial size and O(log2 n) depth.

In this paper we define graph grammars, called the node-replacement graph grammars with path-controlled embedding (nPCE grammars), which use a sequence of edges instead of a single edge to embed a newly replaced graph into the host graph. Then we show that there exists a class of nPCE grammars generating a class of graph languages which is equal to the class of context-free array languages under some stipulations. It means that the path-controlled embedding brings no significant contexts into the production rules. Then, we characterize the above-mentioned class of nPCE grammars by making use of the partial path group.

Node-label controlled graph grammars (NLC grammars) are a mechanism to generate sets of graphs (called graph languages). This paper examines the generating power of NLC grammars with a restricted connection relation and some closure properties of the class of NLC languages. Also, a modified language generating mechanism for NLC grammars is introduced, and the resulting class of graph languages is compared to the class of NLC languages. All results are based on grammars with one-letter terminal alphabets.

A semi-conditional grammar is a context-free grammar whose rules have two associated strings, w1, w2, and such a rule can be applied to a sentential form w only when w1 is a substring of w but w2 is not a substring of w. The paper investigates the generative capacity of such grammars. It is proved that semi-conditional grammars with very short conditions w1, w2 characterize the context-sensitive languages (recursively enumerable languages when λ-rules are allowed). Moreover, when a further restriction in derivation is added (leftmost derivation, ordered, programmed, matrix or regular control restrictions), then also semi-conditional grammars with only forbidding conditions (w1 missing) or with only permitting conditions (w2 missing) again characterize the context-sensitive languages (recursively enumerable, when λ-rules are used).

We apply certain technical results, published in the first part of the present work to obtain reductions between equivalence problems for simple deterministic tree grammars recursive program schemes and the (open) equivalence problem for DPDA's.

Several models of ‘graph grammars’ have been studied with the objective of generating graphs from graphs using a finite set of derivation rules. In this way, possibly infinite sets of graphs (called graph languages) can be finitely defined. One aspect that must be addressed in any such model is the ‘embedding problem’, that is: When a production is applied, how does the new subgraph get reconnected to the original graph? Node-label controlled (NLC) grammars solve this problem in an elegant way that depends only on the labels of nodes in the new and original graphs. This paper examines certain restrictions on NLC grammars similar to the Chomsky or Greibach normal forms for context-free string grammars. For example, one restriction we consider requires each production to produce a terminal labeled node—similar to Greibach normal form. We also consider restrictions on the form which the embedding mechanism can take. Our result is that each of the restrictions we examine causes a reduction in generating power for the grammars. Finally, we discuss some directions for future research on NLC grammars.

Several definitions of the LR(k) grammars can be found in the literature. Since the left-corner grammars can be defined as a restricted class of LR(k) grammars, there are also several definitions are not equivalent. A characterization of the LC(0) languages is given in terms of the simple deterministic languages and these classes of languages are compared with other classes of languages, such as the LL(1) languages and the LR(0) languages.

A 1S grammar generalizes a context-free grammar in the following way: a production A → α can be applied to a string uAv (to rewrite the designed occurence of A) provided that all letters from u belong to a fixed alphabet X and all letters from v belong to a fixed alphabet Z (the alphabets X and Z are independent of the production). It is proved that a language is generated by a 1S grammar if and only if it is context-free: this solves an open problem from the theory of selective substitution grammars (Kleijn and Rozenberg, 1981/82).

Two simple but powerful tools are introduced in LR theory, viz. item grammars and parsing automata. Parsing automata are used to define a large class of correct prefix parsers operating in linear time. DeRemer's and Pager's parsing methods turn out to be special cases. LL and LC tests, as well as inclusion theorems for the classes of LL, LC, and LR grammars will be based on parsing automata, too.

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.

Two new proofs of the fact that proper left-recursive grammars can be covered by non-left-recursive grammars are presented. The first proof is based on a simple trick inspired by the over ten-year-old idea that semantic information hanged on the productions can be carried along in the transformations. The second proof involves a new method for eliminating left recursion from a proper context-free grammar in such a way that the covering grammar is obtained directly.

We investigate the complexity of a variety of normal-form transformations for extended context-free grammars, where by extended we mean that the set of right-hand sides for each nonterminal in such a grammar is a regular set. The study is motivated by the implementation project GraMa which will provide a C++ toolkit for the symbolic manipulation of context-free objects just as Grail does for regular objects. Our results generalize known complexity bounds for context-free grammars but do so in nontrivial ways. Specifically, we introduce a new representation scheme for extended context-free grammars (the symbol-threaded expression forest), a new normal form for these grammars (dot normal form) and new regular expression algorithms. Copyright 2001 Elsevier Science B.V.

We show that, in the case of context-free programmed grammars with appearance checking working under free derivations, three nonterminals are enough to generate every recursively enumerable language. This improves the previously published bound of eight for the nonterminal complexity of these grammars. This also yields an improved nonterminal complexity bound of four for context-free matrix grammars with appearance checking. Moreover, we establish an upperbound of four on the nonterminal complexity of context-free programmed grammars without appearance checking working under leftmost derivations of type 2. We derive nonterminal complexity bounds for context-free programmed and matrix grammars with appearance checking or with unconditional transfer working under leftmost derivations of types 2 and 3, as well. More specifically, a first nonterminal complexity bound for context-free programmed grammars with unconditional transfer (working under leftmost derivations of type 3) which depends on the size of the terminal alphabet is proved.

Infinite sets of terms appear frequently at different places in computer science. On the other hand, several practically oriented parts of logic and computer science require the manipulated objects to be finite or finitely representable. Schematizations present a suitable formalism to manipulate finitely infinite sets of terms. Since schematizations provide a different approach to solve the same kind of problems as constraints do, they can be viewed as a new type of constraints. The paper presents a new recurrent schematization called primal grammars. The main idea behind the primal grammars is to use primitive recursion as the generating engine of infinite sets. The evaluation of primal grammars is based on substitution and rewriting, hence no particular semantics for them is necessary. This fact allows also a natural integration of primal grammars into Prolog, into functional languages or into other rewrite-based applications. Primal grammars have a decidable unification problem and the paper presents a unification algorithm for them that produces finite results. This unification algorithm is proved sound and complete, and it terminates for every input.

It is known that linear apex NLC (Lin-A-NLC) grammars can generate NP-complete graph languages. The present paper examines the source of this expressive power by analyzing complexity and decidability of the so-called k-connecting Lin-A-NLC (k-Lin-A-NLC) grammars in which the right-hand side of each production contains at most k nodes that can be connected to outside nodes. The number of connecting nodes is indeed one source of the expressive power of graph grammars in that k-Lin-A-NLC ⊊(k+1)-Lin-A-NLC for every k≥0. There exists a 2-Lin-A-NLC language which is NP-complete but every 1-Lin-A-NLC language is in NLOG. The equivalence problem is undecidable for 1-Lin-A-NLC languages but is decidable for 0-Lin-A-NLC languages (even when one of two input languages is an arbitrary B-NLC language).