On Growing Context-Sensitive Languages

Gerhard Buntrock^{∗}  Krzysztof Loryś^{∗}^{†}

Report No. 38 January, 1992

Abstract

Growing context-sensitive grammars (GCSG) are investigated. The variable membership problem for GCSG is shown to be NP-complete. This solves a problem posed in [DW86]. It is also shown that the languages generated by GCSG form an abstract family of languages and several implications are presented.

∗Institut für Informatik, Universität Würzburg, D-8700 Würzburg, Germany.

†Instytut Informatyki, Uniwersytet Wrocławski, 51-151 Wrocław, Poland (permanent address). This research was supported by the Humboldt Foundation.

1 Introduction

It is well known that the class of languages generated by context-sensitive grammars is equal to NSPACE(n) and that, even for fixed grammars, the membership problem can be PSPACE-complete. On the other hand the context-free grammars are known to have, for many applications, too weak derivative power. While many modifications extending context-free grammars have been studied, only a few papers concern some restricted versions of context-sensitive grammars. Book ([Boo73]) investigated context-sensitive grammars with certain restrictions on the allowed context or on the use of rewriting rules and showed that some of them cause the grammars to generate only context-free languages. On the other hand when we put the restriction only on the length of derivations to be linear then the context-sensitive grammars are still very powerful, namely they can generate NP-complete languages ([Boo78]).

In [DW86] Dahlhaus and Warmuth considered grammars with only growing rules, i.e. rules whose right side is longer than the left side. This restriction naturally bounds the length of derivations by the length of derivated words. They showed that such growing grammars have the membership problem solvable in polynomial time and even contained in the class of problems logspace-reducible to context-free languages. We denote this class with LOGCFL and refer to [Sud78, Ven91]. With a careful examination of their proof one can get a stronger result: the membership problem for growing grammars is contained in 1-LOGCFL, the class of problems reducible to context-free languages via logspace reductions in which the input is read in one-way mode. The class 1-LOGCFL was introduced by Lautemann ([Lau88]) and by its automata characterization it is known to be a proper subclass of LOGCFL ([Bra77, Lau88]).

Dahlhaus and Warmuth have posed a problem to determine the complexity of the “variable” membership problem for growing grammars, i.e. the problem in which not only the tested word but also a growing grammar is a parameter. We solve this problem by proving (via generic reduction) its NP-completeness. The reduction is of low complexity, namely one-way log space. For such one-way reductions see [HIM78, All88].

Having a very elegant and simple definition growing grammars appear at the first look to generate not an interesting class of languages. In particular, this class (we denote it by GCSL) seemed to be not closed under such basic operations as intersection with regular sets or inverse homomorphism. We refute this opinion and show that GCSL forms an abstract family of languages. This allows us to give a characterization of GCSL by means of weighted grammars. With each such a grammar there is an associated function determining weights of all terminal and nonterminal symbols, and by a natural extension also weights of strings. If we restrict grammars to have only productions with the weight of the right side greater than the weight of the left side then they derive exactly GCSL. Since such weighted grammars allow derivations to have a linear length, it is often much easier to check a membership of a language in the class GCSL via constructing a weighted grammar than via constructing a growing one.

We believe that GCSL is an important class of languages and deserves to be thoroughly studied. With our paper we hope to increase an interest in it. In the last section we give some questions which seem to be worth of considerations.

2 Preliminaries

We assume the reader to be familiar with elementary formal language theory and computational complexity theory, and use the notations standard according to [HU79]. Here we recall only the notions which are basic for our purposes.

A grammar is a quadruple ⟨N, T, S, P ⟩, where N and T are finite, disjoint alphabets of nonterminal and terminal (respectively) symbols, S ∈ N is a start symbol and P is a finite set of productions of the form α → β with α, β ∈ (N ∪ T)^{∗}. The grammars with |α| ≤ |β| for all productions from P are called context-sensitive.

By replacing the above inequality by a sharp one we obtain growing context-sensitive grammars.

Definition 1 A context-sensitive grammar G = ⟨N, T, S, P ⟩ is growing if S does not appear on the right side and |α| < |β| for any (α → β), α ≠ S from P. We denote the growing grammars by GCSG and the class of languages generated by such grammars by GCSL.

By a growth ratio of a production α → β we mean the ratio |α| ; |β|. It is often convenient to deal with GCSG in the following form, which productions, excepting those with S on the left side, have a normalized growth ratio.

Definition 2 We call a growing context-sensitive grammar G = ⟨N, T, P, S⟩ k-normal if all productions have one of the following form:

(1) S → β, where β ∈ T^{∗} and |β| ≤ k

(2) S → β, where β ∈ (T ∪ N)^{k}

(3) α → β, where α, β ∈ (T ∪ N)^{∗}, |α| = k and |β| = k + 1

Proposition 3 For each language L ∈ GCSL there exists a number k_{o} such that for all k ≥ k_{o} there exists a k-normal growing context-sensitive grammar G_{k} such that L = L(G_{k}).

Proof. Let G = (N, T, P, S) be a growing context-sensitive grammar. We set k_{o} to be equal max{|α| : (α → β) ∈ P for some β}.

The productions of G_{k} are divided into two subsets P_{0} and P_{1}. To P_{0} we put all productions S → β of the form 1 and 2 (from Definition 2 such that β can be derived from S in the grammar G. The subset P_{1} we create in two stages. At the beginning we put into it all productions α → β from P with α ≠ S, and then we normalize the length of the left and the right side of each of them.

– “Normalization of α”: each α → β in P_{1} we replace by productions α_{1}αα_{2} → α_{1}βα_{2} for each α_{1}α_{2} ∈ (T ∪ N)^{∗} such that |α_{1}αα_{2}| = k.

– “Normalization of β”: each production a_{1}a_{2}...a_{k} → b_{1}b_{2}...b_{k}b_{k+1}...b_{k+c} we replace by productions

a_{1}a_{2}...a_{k}  → b_{1}B_{2}...B_{k+1},
B_{i}B_{i+1}...B_{k+i−1} → b_{i}B_{i+1}...B_{k+i} for i = 2, ..., c − 1,
B_{c}...B_{k+c−1}  →  b_{c}...b_{k+c},

where B_{i} (for i = 2, ..., k + c − 1) are unique new nonterminals.

It is clear that G_{k} and G are equivalent. □

The restriction imposed on the growth ratio to be greater than one for all productions in /GCSG/ implies that all derivations in these grammars are not longer than the derivated word. This requirement is relaxed in quasi-growing grammars.

Definition 4 A grammar G = ⟨N, T, S, P ⟩ is quasi-growing if there exists a function f : (N ∪T) → N (here N stands for the set of positive integers) such that for all productions (α → β) ∈ P it holds f(α) < f(β), where f(a_{1}...a_{n}) = ∑_{i=1}^{n} f(a_{i}) for a_{1}...a_{n} ∈ (N ∪ T)^{∗}. The set of quasi growing grammars we denote by QGG.

A similar concept of weight functions was already used in string rewriting ([Jan88]). It is easy to see that derivations in QGG have length only linearly depending on the length of derivated words. However, in Theorem 19 we show that quasi-growing grammars derive exactly GCSL.

For context-sensitive grammars there are some well known simple normal forms. The following form was proposed by Cremers ([Cre73]):

Definition 5 A context-sensitive grammar is in Cremers’ normal form if all productions are of the forms

\begin{matrix}AB & ⟶ & CD \\ A & ⟶ & CD \\ A & ⟶ & a \end{matrix}

where A, B, C, D are nonterminals and a is a terminal.

Obviously such a normal form is not growing. From Theorem 19 it follows that for every QGG G there exists an equivalent grammar G′ in Cremers’ normal form; however, the size of G′ can be much bigger (even exponentially) than the size of G. The next proposition shows that for a QGG with only length-nondecreasing productions such a normal form can be efficiently obtained.

Proposition 6 For every QGG an equivalent quasi-growing grammar in Cremers’ normal form can be constructed in polynomial time.

Proof. Let G = ⟨N, T, S, P ⟩ be a quasi-growing grammar with only length-nondecreasing productions and let f be a corresponding weight function. We can assume that G does not contain productions of the form α → β with |α| = |β| = 1. A grammar in Cremers’ normal form we obtain by replacing all productions from P which are not in a good form by an equivalent sequence of productions.

Let suppose that a_{1}...a_{k} → b_{1}...b_{l} is a production from P, k ≥ 2. We differentiate between two cases:

(1) l ≥ k + 2

(2) l = k or l = k + 1

In the first case we take the following sequence of productions:

a_{1}a_{2} → dA_{2}
A_{i}a_{i+1} → dA_{i+1}  for i = 2, ..., k − 1
A_{k}  → B_{k}B_{k+1}
dB_{i} → B_{i−1}b_{i} for i = 2, ..., k − 1
dB_{2} → b_{1}b_{2}
B_{i} → b_{i}B_{i+1} for i = k + 1, ..., l − 2
B_{l−1} → b_{l−1}b_{l}

The symbols d, A_{i} (for i = 2, ..., k) and B_{i} (for i = 2, ..., l − 1) are new nonterminals with the following weights:

f(d) = 1
for i = 2, ..., k :
f(A_{i}) = f(a_{1}...a_{i})
f(B_{i}) = f(b_{1}...b_{i}) − 2(i − 1)
and for i = k + 1, ..., l − 1 :
f(B_{i}) = f(b_{i}...b_{l}) − l + i

Note that, without loss of generality, we can assume that f(α) ≤ f(β) − (|α| + |β| − 2) for each production α → β from P. If f does not fulfill this condition then instead of f one can take the function f′ = c · f, where c = max{|α| + |β| − 2 : α → β ∈ P }.

Now it is easy to check that all above productions are growing with respect to the function f.

For the second case a corresponding sequence of productions can be obtained in an analogous way, so we omit this construction as well as an easy proof of the equivalence of such obtained grammar and grammar G.

From this construction follows that the number of rules will be linear bounded in the length of the encoded grammar G. Hence we see that easily a polynomial time-bounded algorithm can be obtained. □

At the end of this section we recall the notion of abstract family of languages.

Definition 7 A family of languages is a collection of languages containing at least one nonempty language. An abstract family of languages (AFL) is a family of languages closed under union, concatenation, iteration, intersection with regular languages, ε-free homomorphism and inverse homomorphism.

It is well known that the “AFL operations” are not independent. In Section 4 we will make use of the following proposition (see [GGH69]).

Proposition 8 Let F be a family of languages. If F is ε-free and closed under concatenation, ε-free homomorphism and inverse homomorphism, then F is closed under intersection with regular sets.

3 The complexity of the membership problem for variable grammars

The variable membership problem consists in determining, for given a word w and a grammar G, whether w ∈ L(G). It is known that for context-sensitive grammars this problem is PSPACE-complete. The open problem posed in [DW86] was to determine its complexity for growing context-sensitive grammars; more precisely, Dahlhaus and Warmuth asked whether this problem can be solved in polynomial time or whether it is NP-complete. The polynomial time algorithm, given by them, for the membership problem with fixed grammars, adapted for the problem with variable grammars, would work in superpolynomial time because the degree of the polynomial bounding its complexity is dependent on the grammar and can be arbitrary large. We give here a strong argument that this problem presumably is intractable, showing that it is NP-complete under a weak type of reducibility, namely one-way logspace (see [HIM78, All88] for more information about this type of reducibility).

Let Ḡ denote a word coding a grammar G. Our problem consists in determining the complexity of the language

L_{GCSL} = {⟨Ḡ, w⟩ : G is a growing context-sensitive grammar and w ∈ L(G)}.

As a function coding grammars can be taken any reasonable one, we will not specify it. The same concerns also a function coding configurations of Turing machines that will be used later in the proof of NP-hardness of the language L_{GCSL}.

Proposition 9 L_{GCSL} ∈ NP.

Proof. Let ⟨Ḡ, w⟩ ∈ L_{GCSL} and let c be the maximal length of the code of a single symbol from G. Clearly, c < |Ḡ|. Since w is derived in no more than |w| steps and the length of the longest phrase in any derivation of w is bounded by c|w| < |Ḡ| · |w|, it is easy to construct a nondeterministic algorithm which simulates derivations in G in time |w|^{2} · |Ḡ|^{2} < |⟨Ḡ, w⟩|^{4}. □

Now we show how, for each polynomial-time bounded nondeterministic Turing machine M, one can construct growing context-sensitive grammars G_{w,M} such that each L(G_{w,M}) is over one-letter alphabet and it is nonempty if and only if M accepts w. Moreover, in this case the length of the shortest word in L(G_{w,M}) is bounded by a polynomial in |w|.

Let T_{1} be an alphabet in which configurations of Turing machines are coded. We assume that #, [,] ∉ T_{1}. For simplicity, from now on, we do not distinguish between objects like configurations and productions and their codes. We define

Seq_{w,M} = { [l_{1}#k_{2}][l_{2}^{R}#k_{3}^{R}][l_{3}#k_{4}][l_{4}^{R}#k_{5}]...[l_{p−1}^{R}#k_{p−1}^{R}][l_{p−1}#k_{p}] :

∀_{2≤i≤p−1} k_{i} and l_{i} are M’s configurations such that l_{i} is a successor of k_{i}, l_{1} is the initial configuration of M when w is an input, k_{p} is a predecessor of an accepting configuration and p is an even natural number }.^{1}

The following proposition can be easily seen.

Proposition 10 For any Turing machine M and a word w the language Seq_{w,M} can be generated by a context-free grammar F_{w,M} = ⟨N_{1}, T_{1} ∪ {#, [,]}, S, P_{w,M}⟩. Moreover, for any fixed M there exists a GSM ^{2} which having w as an input produces a code of F_{w,M}.

A key part of the grammar G_{w,M} is a subset H_{k} (k = |w|) of its productions which, roughly speaking, allows checking whether corresponding subwords are equal. More precisely, starting from a word [l_{1}#k_{2}][l_{2}^{R}#k_{3}^{R}][l_{3}#k_{4}][l_{4}^{R}#k_{5}]...[l_{p−1}^{R}#k_{p−1}^{R}][l_{p−1}#k_{p}] ∈ Seq_{w,M} and using productions from H_{k} one can derive a terminal word if and only if for all i with 1 ≤ i < p it holds l_{i} = k_{i+1}. Note that H_{k} is common for all grammars G_{w,M} with |w| = k.

Let N_{2} = T_{1} ∪ T̄_{1} ∪ {[,], #, C} be an alphabet of nonterminal symbols such that T̄_{1} = {ā : a ∈ T_{1}} and let T_{2}, a terminal alphabet, consist of only one letter d. For every a, b ∈ T_{1}, to the system H_{k} belong the following productions:

1By l^{R} we denote the reversal of the string l.

2General sequential machine, i.e. a deterministic finite one-way automaton with output, see[HU79] page 272 for an exact definition

(1)  [a → [Cā
(2)  Cād^{i}b → d^{i+1}bCā, ∀_{0≤i<k}
(3) Cā#d^{4i}a → #d^{4(i+1)}, ∀_{0≤i<k}
(4) [d^{i} → d^{i+1}[, ∀_{0≤i<k}
(5)  [# → dd[
(6)  [ ] → ddd
(7)  d → dd.

Proposition 11 H_{k} consists of k(r^{2} + r + 1) + r + 3 productions, where r = |T_{1}|.

Proposition 12 Let u = [u_{1}#v_{1}][u_{2}#v_{2}] ... [u_{s}#v_{s}], u_{i}, v_{i} ∈ T_{1}^{∗} for i = 1, ..., s. If a terminal word can be derived from u using production from H_{k} then for all i with 1 ≤ i ≤ s it holds u_{i} = v_{i}.

Proof.(sketch) The only way of removing # and [ from a phrase, being derived, is to apply the productions (5) and (6), respectively. Before this can be done, each letter of u_{i} has to be changed via production (1) into its counterpart from T_{2} and then transported via production (2) to #, where it is compared with the corresponding letter of v_{i}. Since there is no production changing the order of transported letters it is clear that u_{i} = v_{i}. □

Proposition 13 From each word [w#w], ( w ∈ T_{1}^{∗}, |w| ≤ k ), system H_{k} derives d^{l}, for

any l ≥ (|w|+9)(|w|+2) ; 2.

Proof. Let w = a_{1}a_{2}...a_{n}, n ≤ k. One can easily show by induction that for all i, 1 ≤ i ≤ n

[w#w] ⟹^{∗} d^{i^{2}+i−2 ; 2} [a_{i}d^{i−1}a_{i+1}d^{i−1}...d^{i−1}a_{n}#d^{4(i−1)}a_{i}a_{i+1}...a_{n}].

Thus finally

[w#w] ⟹^{∗} d^{n^{2}+3n ; 2} [#d^{4n}] ⟹^{∗} d^{n^{2}+3n ; 2 +2}[d^{4n}] ⟹^{∗} d^{(n+9)(n+2) ; 2} .

Now, for l > (n+9)(n+2) ; 2, the words d^{l} can be derived by use of production (7). □

Theorem 14 The variable membership problem for growing context-sensitive Grammars i.e. the language L_{GCSL}, is NP-complete under one-way logspace reducibility.

Proof. By Proposition 9 it is sufficient to show that L_{GCSL} is one-way logspace hard for NP.

Let M be a nondeterministic Turing machine working in time p(n). Without loss of generality we can assume that there exists a polynomial p′(n) which bounds the length of codes of the configurations entered by M within p(n) steps. Let N_{1}, S and P_{w,M} be from F_{w,M} (see Proposition 10) and let N_{2} and H_{p}(|w|) be as described above. We set

G_{w,M} = ⟨N_{1} ∪ N_{2}, {d}, S, P_{w,M} ∪ H_{p(|w|)}⟩

and

t_{M}(w) = ⟨G_{w,M}, d^{(p′(|w|)+9)(p′(|w|)+2)p(|w|)}⟩.

All productions from H_{p(|w|)} are polynomially bounded in length and have very simple form. This, together with Proposition 10, gives that t_{M} can be constructed to be a one-way logspace transducer.

Since all productions from H_{p(|w|)} contain no symbol from N_{1} and P_{w,M} consists of context-free rules, each derivation in G_{w,M} can be transformed into an equivalent one in which no production from H_{p(|w|)} is applied before any production from P_{w,M}. From this and Proposition 13 it is easy to see that w ∈ L(M) ⇔ L(G_{w,M}) is nonempty ⇔ d^{(p′(|w|)+9)(p′(|w|)+2)p(|w|)} ∈ L(G_{w,M}). □

Let us note that the languages G_{w,M} can be changed so they would be either empty or would contain at most one word from {d}^{∗}. Thus the variable membership problem for GCSG remains NP-complete even for some restricted subclasses of GCSL.

4 Closure properties

In this section we show that the class GCSL is closed under all six AFL operations. A nontrivial part of the proof (Proposition 17) concerns the closure under inverse homomorphism. As a consequence we obtain a characterization of GCSL by quasi-growing grammars (Theorem 19).

Proposition 15 The class GCSL is closed under union, concatenation, iteration, substitution and ε-free homomorphism.

Proof. By standard methods using the fact that for any language L ∈ GCSL there exists a growing context-sensitive grammar G generating L such that terminal symbols appear only on the right side of productions. □

To prove that GCSL is an AFL it is now sufficient, by Propositions 15 and 8, to show that it is closed under inverse homomorphism.

We start with defining some notions which will be useful in the proof of this fact. Following [Loe70, DW86] with each derivation in G = ⟨N, T, S, P ⟩ we associate a planar acyclic graph called a derivation graph. The vertices in such a graph are labeled by corresponding symbols and productions used in the derivation. The label of a vertex v we denote by l(v). For a derivation α_{1} ⟹ ∗_{G} α_{2} ⟹ ∗_{G} ... ⟹ ∗_{G} α_{k} the derivation graph D_{k} = (V_{k}, E_{k}) is defined inductively. At each step the sources of V_{i} correspond to α_{1} and sinks correspond to α_{i}.

(1) if α_{1} = a_{1}a_{2}...a_{r} then D_{1} = ({v_{j} : j = 1, ..., r and l(v_{j}) = a_{j}},◯̸).

(2) if α_{i−1} = wαw′ ⟹ wβw′ = α_{i} and α = a_{1}a_{2}...a_{r}, β = b_{1}b_{2}...b_{s} then

– V_{i} = V_{i−1} ∪ {v^{i}, v_{1}^{i}, ..., v_{s}^{i}}, where v^{i} and v_{j}^{i} are new vertices, v^{i} is labeled by the production (α → β) and l(v_{j}^{i}) = b_{j} for j = 1, ..., s,

– E_{i} = E_{i−1} ∪ {(v^{i}, v_{j}^{i}) : j = 1, ..., s} ∪ {(u_{j}, v^{i}): j = 1, ..., s} where u_{1}, u_{2}, ..., u_{r} ∈ V_{i−1} correspond to α.

Let D be a derivation graph corresponding to z ⟹ ∗_{G} u. We say that a subgraph F ⊆ D is autonomous if:

(1) considered as an undirected graph F is connected,

(2) all predecessors of F ’s vertices also belong to F, (3) all sinks of F are labeled by productions.

Let v_{1}, ..., v_{s} be the sequence of all sources of F and let v′_{1}, ..., v′_{s′} be the sequence of all successors of F ’s sinks (remind that there is a natural order among the sources and among the sinks due to planarity of D). The word l(v_{1})...l(v_{s}) we call a base of F and the word l(v′_{1})...l(v′_{s′}) we call a derivative of F. It is easy to see that the base is a subword of z and that D \ F is a derivation graph of some derivation z′ ⟹ ∗_{G} u, where z′ is created by replacing the base with the derivative.

If v is a node labeled by a production then by I(v) we denote the subgraph of D induced by v and the set of its ancestors. It is easy to see that I(v) is autonomous for any v.

By a size of autonomous subgraph we mean the number of its vertices labeled by productions.

Proposition 16 Let D be a derivation graph for some derivation in k-normal growing context-sensitive grammar.

(1) For any vertex v ∈ D the subgraph I(v) has the base of length not greater that (2h − 1) · k − 2(h − 1), where h is the depth of v.

(2) One of the following conditions is fulfilled:

(a) there exists an autonomous subgraph F in D of the size at least k and the base not longer than 4k(k − 1)

(b) all autonomous subgraphs of D have size smaller than k.

Proof. We omit an easy proof of the part (1).

To prove (2) let us suppose that there exists a subgraph F ⊆ D of the size at least k and the base longer than 4k(k − 1). If F contains a vertex v of the depth k then I(v) satisfies the conditions of the point 1. So let us suppose that all vertices of F have depth not greater than k −1. We say that a sink of F is maximal if none of its successors belong to F. Let v_{1}, ..., v_{r} be succeeding maximal sinks of F. Let now F′_{i} = ⋃_{j=1}^{i} I(v_{j}). From (i) it follows that the first F′_{i} of the size at least k has the base not longer than 4k(k − 1). □

Proposition 17 The class GCSL is closed under inverse homomorphism.

Proof. Let L ⊆ Σ^{∗} be a growing context-sensitive language, let h : Δ^{∗} → Σ^{∗} and let l =max{|h(a)|: a ∈ Σ}. Since GCSL is closed under substitution it is sufficient to prove the theorem for ε-free h. Namely, if Δ_{1} = {a ∈ Δ : h(a) = ε} and Δ_{2} = Δ \ Δ_{1} are not empty, then h_{1} = h|_{Δ_{2}} is ε-free and h^{−1}(L) = S(h_{1}^{−1}(L)), where S is a substitution such that S(a) = Δ_{1}^{∗}aΔ_{1}^{∗} for each a ∈ Δ_{2}.

By Proposition 3 there exists a k-normal grammar G = ⟨N, Σ, P, S⟩ generating L for some k > 2l. Now we define a new growing context-sensitive grammar G′ = ⟨N′, Δ, P′, S′⟩ and then we show that L(G′) = h^{−1}(L).

We set N′ = N_{1} ∪N_{2}, where N_{1} = (N ∪Σ)^{k} and N_{2} = ⋃_{i=1}^{l−1} ⋃_{j=1}^{k−1} Σ^{i} ×(N ∪Σ)^{j}. The set P′ of productions is divided into four subsets P_{i} for i = 0, .., 3. In the description of these subsets we use the following natural projection from N′ onto N^{∗}: C(⟨a_{1}, a_{2}, ..., a_{j}⟩) = a_{1}a_{2}...a_{j} for each ⟨a_{1}, a_{2}, ..., a_{j}⟩ ∈ N′.

Now we define

P_{0} = {S′ → w : w ∈ Δ^{∗}, |h(w)| ≤ 4k(k − 1) and S ⟹ ∗_{G} h(w)},
P_{1} = {S′ → β : β ∈ (N′)^{4(k−1)} and S ⟹ ∗_{G} C(β)},
P_{2} = {α → β : α ∈ (N′)^{4(k−1)}, β ∈ (N′)^{4(k−1)+1} and C(α) ⟹ ∗_{G} C(β)}

and

P_{3} = {t_{1}α → wt_{2} : t_{1}, t_{2} ∈ N_{2} ∪ {ε}, α ∈ (N′)^{m}, m ≤ 4(k − 1), w ∈ Δ^{∗}
and h(w)C(t_{2}) is derivable in G from C(t_{1}α) in less than k
steps. }

Let us note that |wt_{2}| > |t_{1}α| for all (t_{1}α → wt_{2}) ∈ P_{3}, so G′ is growing.

One can easily prove by induction on the length of derivation that all phrases derived from S′ have form α_{1}w_{1}α_{2}w_{2}...w_{s−1}α_{s}, where all α’s are from (N′)^{∗}, all w’s are from Δ^{∗}

and S ⟹ ∗_{G} C(α_{1})h(w_{1})C(α_{2})h(w_{2})...h(w_{s−1})C(α_{s}).

Therefore w ∈ L(G′) ⇒ ∃_{u∈L}h(w) = u.

Thus it remains to prove that h^{−1}(L) ⊆ L(G′).

Let w ∈ h^{−1}(L) and let u ∈ L be such that h(w) = u. If |u| ≤ 4k(k − 1) then w is derived by a production from P_{0}. So let assume that |u| > 4k(k − 1) and let u_{1} be such that S ⟹ ∗_{G} u_{1} ⟹ ∗_{G} u and |u_{1}| = 4k(k − 1). Of course, there exists z_{1} ∈ (N′)^{4(k−1)} such that C(z_{1}) = u_{1}, so S′ → z_{1} is in P_{1}. Let F be a derivation graph for u_{1} ⟹ ∗_{G} u. If F contains an autonomous subgraph of the size at least k (by Proposition 16 we can assume that its base is not longer than 4k(k − 1)), then repeating an appropriate number of times an operation of removing a maximal sink from the subgraph we can obtain a subgraph F′ ⊆ F of the size k. Clearly, F′ corresponds to a sequence of k productions which applied to the base of F derive from the word u_{1} a word u_{2} such that u_{2} ⟹ ∗_{G} u. By the definition of the set P_{2} we have that z_{1} ⟹_{G’} z_{2}, where C(z_{2}) = u_{2}. Applying this consideration recursively to u_{2} and to the graph F \ F′ we can finally show that there exist words u_{x} ∈ (N ∪ Σ)^{∗} and z_{x} ∈ (N′)^{∗} such that

(1) S′ ⟹ ∗_{G’} z_{x},

(2) C(z_{x}) = u_{x},

(3) u_{x} ⟹ ∗_{G} u and all autonomous subgraphs of the corresponding derivation graph H are of size < k.

Since the autonomous subgraphs of H have basis not longer than k + (k − 1)(k − 2), the words u_{x} and u can be divided into subwords u_{x}^{1}, ..., u_{x}^{r} and u_{1}, ..., u_{r}, respectively, such that ∀_{1≤i≤r}k ≤ |u_{x}^{i}| ≤ 2k + (k − 1)(k − 2) and u_{i} is derived from u_{x}^{i} in less than k steps.

Now for each i = 1, ..., r we define w_{i}, s_{i}, z_{j_{i}}, zj_{i}^{′}, zj_{i}^{′′}, t_{i} as follows:

– w_{i} is the maximal prefix of w such that h(w_{i}) is a prefix of u_{1}u_{2}...u_{i},

– s_{i} is the suffix of u_{1}u_{2}...u_{i} such that u_{1}u_{2}...u_{i} = h(w_{i})s_{i},

– if z_{x} = z_{1}z_{2}...z_{y}, where z_{1}, ..., z_{y} ∈ N′, then C(z_{j_{i}}) = zj_{i}^{′}zj_{i}^{′′} and u_{x}^{1}...u_{x}^{i} = C(z_{1}...z_{j_{i}−1})zj_{i}^{′}.

– t_{i} ∈ N_{2} ∪ {ε} is such that C(t_{i}) = s_{i}zj_{i}^{′′} (note that t_{r} = ε).

One can observe that the following derivation is possible due to productions from P_{3}:

z_{x} ⟹_{G’} w_{1}t_{1}z_{j_{i}+1}...z_{y} ⟹_{G’} w_{1}w_{2}t_{2}z_{j_{2}+1}...z_{y} ⟹ ∗_{G’} w_{1}w_{2}...w_{r} = w

□

Now we are ready to state the main theorems of this section:

Theorem 18 The class GCSL forms an AFL.

Proof. By the propositions 8, 15, and 17 GCSL is closed under all six AFL operations.

□

Theorem 19 The languages producible by QGGs and GCSGs are the same.

Proof. Each GCSG can be seen as a QGG simply with a constant weight function.

Let L be generated by a quasi-growing grammar G = ⟨N, T, S, P ⟩ with weight function f. Without loss of generality we can assume that S does not appear on the right side of any production and that f(S) = 1.

Let c ∉ N ∪ T and let h be a homomorphism such that h(a) = ac^{f(a)−1} for each a ∈ N ∪ T. Then G′ = ⟨N ∪ {c}, T, S, P′⟩, where P′ = {h(α) → h(β) : (α → β) ∈ P } is a growing context-sensitive grammar and L(G) = h^{−1}(L(G′)). □

5 Conclusions and open problems

A disadvantage of the class of growing context-sensitive languages is that, being a subset of linear context-sensitive languages, it does not contain some very simple languages like L̃ := {ww^{R}w : w ∈ Σ^{∗}} ([Gla64]). It would be interesting to find a natural extension of context-sensitive grammars which on the one hand would allow to derive such languages but on the other hand would not lead the membership problem outside LOGCFL.

Another interesting problem concerns the intersection hierarchy for GCSL, i.e. the hierarchy of classes GCSL^{i} = {L : ∃_{L_{1},L_{2},...,L_{i}∈GCSL} L = ⋂_{j=1}^{i} L_{j}}, for i ≥ 1. It is easy to see that the language L̃, defined above, separates the first two levels of the hierarchy and that ⋃_{j=1}^{∞} GCSL_{j} ⊆ LOGCFL. An analogous hierarchy for context-free languages was shown to be infinite ([LW73]). We conjecture that it is also infinite for GCSL.

The complexity of GCSL is still not well examined. In contrary to the context-free languages GCSL contain nonregular tally languages. What is their complexity? Can one show that tally languages from GCSL are included in NSPACE(log n)? Also the derivative power of GCSG is not exactly established. Even some very low complexity classes are not known to be included in GCSL. An example of such a class can be the class of languages recognized by one-way deterministic Turing machines in real-time and logarithmic space.

Acknowledgements

Thanks are due to Hans-Jörg Burtschick, Jaime Caro, Diana Emme, Ulrich Hertrampf, Albrecht Hoene, Klaus-Jörn Lange, Heribert Vollmer, and Klaus Wagner for some hints and fruitful discussions on the subject of this paper.

We are gratefull also to Manfred Warmuth who brought to our attention that the variable membership problem was already solved in two technical reports [NK87, CH89].

References

[All88] Eric W. Allender. Isomorphisms and 1-L reductions. Journal of Computer and System Sciences, 36:336–350, 1988.

[Boo73] Ronald V. Book. On the structure of context-sensitive grammar. International Journal of Computer and Information Sciences, 2:129–139, 1973.

[Boo78] Ronald V. Book. On the complexity of formal grammars. Acta Informatica, 9:171–181, 1978.

[Bra77] Franz-Josef Brandenburg. On one-way auxiliary pushdown automata. In 3rd GI Conference on theoretical computer science, volume 48 of LNCS, pages 132–144. Springer, 1977.

[CH89] Sang Cho and Dung T. Huynh. Uniform membership for deterministic growing context-sensitive grammars is P-complete. Technical Report UTDCS-5-89, Computer Science Department, University of Texas at Dallas, Richardson, Texas 75083, February 1989.

[Cre73] A.B. Cremers. Normal forms for context-sensitive grammars. Acta Informatica, 3:59–73, 1973.

[DW86] Elias Dahlhaus and Manfred K. Warmuth. Membership for growing context-sensitive grammars is polynomial. Journal of Computer and System Sciences, 33:456–472, 1986.

[GGH69] Seymour Ginsburg, Sheila Greibach, and John Hopcroft. Studies in Abstract Families of Languages. Memoir #87, American Mathematical Society, 1969.

[Gla64] A.W. Gladkij. On the complexity of phrase structure grammars. Algebra i Logika Sem., 3:29–44, 1964. (in Russian).

[HIM78] Juris Hartmanis, Neil Immerman, and Stephen R. Mahaney. One-way log-tape reductions. In 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 65–71, 1978.

[HU79] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Series in Computer Science. Addison-Wesley, 1979.

[Jan88] Matthias Jantzen. Confluent string rewriting. Springer, 1988.

[Lau88] Clemens Lautemann. One pushdown and a small tape. In Klaus W. Wagner, editor, Dirk Siefkes zum 50. Geburtstag, pages 42–47. Technische Universität Berlin and Universität Augsburg, 1988.

[Loe70] Jacques Loecks. The parsing of general phrase-structure grammars. Information and Control, 16:443–464, 1970.

[LW73] Leonard Y. Liu and Peter Weiner. An infinite hierarchy of intersections of context-free languages. Mathematical Systems Theory, 7:185–192, 1973.

[NK87] Paliath Narendran and Kamela Krithivasan. On the membership problem for some grammars. COINS Technical Report CAR-TR-267 & CS-TR-1787 & AFOSR-86-0092, Center for Automation Research, University of Maryland, College Park, MD 20742, March 1987.

[Sud78] Ivan H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery, 25:405–414, 1978.

[Ven91] H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Sciences, 43:380–404, 1991.