Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1996, Article 4 13 November 1996

ISSN 1073–0486. MIT Press Journals, 55 Hayward St., Cambridge, MA 02142 USA; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://www-mitpress.mit.edu/jrnls-catalog/chicago.html

• http://www.cs.uchicago.edu/publications/cjtcs/

• gopher.mit.edu

• gopher.cs.uchicago.edu

• anonymous ftp at mitpress.mit.edu

• anonymous ftp at cs.uchicago.edu Buntrock and Niemann Weakly Growing CSGs (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}1996 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Stephen Homer  Alan Selman
Jin-Yi Cai Neil Immerman Nir Shavit
Anne Condon  †Paris Kanellakis Eva Tardos
Cynthia Dwork Howard Karloff  Sam Toueg
David Eppstein Philip Klein  Moshe Vardi
Ronald Fagin  Phokion Kolaitis Jennifer Welch
Lance Fortnow Stephen Mahaney Pierre Wolper
Steven Fortune Michael Merritt

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii]

Weakly Growing Context-Sensitive Grammars

Gerhard Buntrock  Gundula Niemann

13 November, 1996

Abstract

This paper introduces weakly growing context-sensitive grammars.

Abstract-1

Such grammars generalize the class of growing context-sensitive grammars (studied by several authors), in that these grammars have rules that “grow” according to a position valuation.

If a position valuation coincides with the initial part of an expo-

Abstract-2

nential function, it is called a steady position valuation. All others are called unsteady. The complexity of the language generated by a grammar depends crucially on whether the position valuation is steady or not. More precisely, for every unsteady position valuation, the class of languages generated by WGCSGs with this valuation coincides with the class CSL of context-sensitive languages. On the other hand, for every steady position valuation, the class of languages generated corresponds to a level of the hierarchy of exponential time-bounded languages in CSL. We show that the following three conditions are equivalent:

• The hierarchy of exponential time-bounded languages in CSL collapses.

• There exists a class defined by an unsteady position valuation such that there is also a normal form of order 2 (e.g., Cremers or Kuroda normal form) for that class.

• There exists a class defined by a steady position valuation that is closed under inverse homomorphisms.

Some of these results were presented at LATIN’95 at Valparaíso, Chile.

1

Buntrock and Niemann Weakly Growing CSGs §1

1 Introduction

A beautiful theory always has simple concepts and remarkable results. Here

1-1

we investigate a widely unknown but nice part of the class of context-sensitive languages (CSL).

Our simple concept consists of a valuation of strings, and concentration

1-2

on the context-sensitive grammars that are growing under such a valuation. As a result, we get characterizations of known double-bounded complexity classes by this quite different concept. Namely, we view the exponential time-bounded languages in CSL, where CSL is the class of languages that can be recognized by a Turing machine in linear space. Little is known about such dual-bounded classes; see, e.g., [Coo79], [Pip79], [Bör89], and [Rei90]. Wolfgang Paul asks in general which kind of speedup theorem holds for spacebounded computations (see [Pau78]). We concentrate on this question for the case of linear-bounded automata. It is shown that this problem can be reformulated using our concept, which comes from formal language theory: We ask whether a particular class of languages is characterized by a class of normal form grammars of order 2 (i.e., left and right sides of rules have length at most 2), or, equivalently, whether another class is closed under inverse homomorphism.

Noam Chomsky has already observed in his famous work that CSL is

1-3

characterized by monotone grammars, that is, grammars in which in every rule a string is replaced by a string that is at least as long as the first one [Cho59]. We will use this characterization as a definition.

By replacing “at least as long as” in the definition of the class CSG of

1-4

context-sensitive grammars by “longer than,” we obtain growing contextsensitive grammars (GCSG) which define the class of growing context-sensitive languages (GCSL). Elias Dahlhaus and Manfred Warmuth investigated the complexity of GCSL and found out that GCSL is contained in LOGCFL [DW86], the class of such languages that can be transformed into a contextfree language (CFL) using logarithmic space ([Sud78], [Ruz80]). Note that LOGCFL is a subclass of the class P of languages recognizable deterministically in polynomial time. If we valuate the symbols of a CSG with a homomorphic mapping into the natural numbers with addition, and demand that in every rule the sum of the values of the symbols increases, this type of grammar (quasi-GCSG, or QGCSG for short) characterizes GCSL ([BL92], [BL94], [Bun96]). Unfortunately, the class GCSL is very weak. Not even the

2 language COPY =^{def} { ww : w ∈ {a, b}^{∗} } is contained in GCSL ([Bun93], see also [BO95]).

Weakly growing context-sensitive grammars (WGCSG) are a generaliza-

1-5

tion of QGCSG. In a WGCSGwe valuate the positions as well as the symbols inside a rule: Every position inside a rule is related to a certain value. The valuation of a side of a rule is obtained by the sum of the products of the symbol valuation and the position valuation for every symbol. A contextsensitive grammar is called weakly growing context-sensitive related to a certain position valuation (WGCSG_{s}, where s stands for the position valuation), if there exists a symbol valuation such that for every rule the valuation of the left-hand side is lower than that of the right-hand side. (This is defined precisely in Definition 2.) The weakly growing context-sensitive languages related to constant position valuations characterize GCSL. We will show that this definition is robust under some natural changes.

The valuation of positions gives the possibility to interchange two sym-

1-6

bols by a rule. This can be used to prove COPY ∈ WGCSL_{s} for every nonconstant position valuation s. On the other hand, it can easily be seen that it is not possible to interchange two symbols back and forth in the same grammar. Thus we know that WGCSG_{s} is strictly contained in CSG for each position valuation s. The question as to whether or not the corresponding language classes are strictly contained in CSL will be viewed later.

For important language classes we expect some essential closure proper-

1-7

ties. Clearly, the closure under non-ε-free homomorphisms of WGCSL_{s} yields the class of all recursively enumerable sets; i.e., WGCSL_{s} is a basis for recursively enumerable sets (the notion of a basis was originally introduced by Raymond Smullyan in [Smu61]). With standard arguments the following can be proved: For every position valuation s, the class WGCSL_{s} is closed under ε-free homomorphism, union, ε-free regular substitution, concatenation, and intersection with regular sets. Additionally it can be shown that WGCSL_{s} is closed under transposition for every position valuation s.

What is missing, e.g., for WGCSL_{s} to be an abstract family of lan-

1-8

guages (or AFL, see any good introduction to formal language theory, such as [Sal73] or [Har78]), is the closure under inverse homomorphism and also under k-bounded homomorphism. Here from [GGH69] it is known that if the one holds, then so does the other and vice versa, because of the closure properties we already know. The closure under inverse homomorphism here can neither be proved nor disproved in general; a main result in this context is the equivalence of this problem to the problem of whether all linear space-

3 bounded automata can be simulated by linear space-bounded automata with an additional universal exponential time bound. The reason for this equivalence lies in the fact that for each nonconstant position valuation, the closure under inverse homomorphism of WGCSL_{s} equals CSL.

To prove these results we distinguish steady and unsteady position valua-

1-9

tions: A position valuation is steady if it coincides with the initial part of an exponential function. We refer to the base of that corresponding function as the growth factor of the position valuation. In the other case, the position valuation is unsteady.

It turns out that steady position valuations are uniquely extendible to

1-10

infinite position valuations such that all strings can be valuated. Moreover, the number of derivation steps can be bounded by the valuation of the derived string. This gives the result that for a steady position valuation every weakly growing context-sensitive grammar related to it can produce only sets acceptable by linear space-bounded automata in a certain exponential time, where the base of the bounding exponential function is the growth factor of the position valuation (if it is monotone increasing). To get this result so tight, we transfer Gladkii’s Connectivity Theorem (see [Gla64]) to WGCSLs. On the other hand, for every language that can be recognized by a linear space-bounded automaton there exists a steady position valuation s such that this language belongs to WGCSL_{s}. To get a very tight relation here, we introduce a new type of counters: grammars that count.

Furthermore, the weakly growing context-sensitive language classes cor-

1-11

responding to different growth factors build up a linearly inclusion-ordered hierarchy that characterizes the exponential time hierarchy for CSL in terms of necessary and sufficient conditions for the hierarchy to collapse.

For unsteady position valuations, there does not exist an infinite extension

1-12

such that the value of a sentential form increases if and only if a weakly growing context-sensitive rule is applied. To the contrary: We present a collection of rules which when applied to a given sentential form lead to a decrement of the value of that sentential form. By this we will show that arbitrarily long derivations are possible. We interpret this to be the reason that for every unsteady position valuation the corresponding class of weakly growing context-sensitive grammars characterizes CSL.

Another important difference between the steady and unsteady cases con-

1-13

sists in the existence of normal forms of order 2. Note that every s-weakly growing context-sensitive grammar in a normal form of order 2 is one related to a steady position valuation. Here we know that for every steady position

4 valuation s and every weakly growing context-sensitive grammar related to it there exists an equivalent WGCSG of the same type in normal form. This can be proved using an obvious transformation. For this we will use Cremers normal form, which has the advantage of having a minimal number of different types of rules. Additionally, it turns out that the growth factor of a steady position valuation characterizes a weakly growing context-sensitive language class and that the language classes corresponding to a growth factor and its reciprocal value coincide. For unsteady position valuations, the obvious transformation to reduce the order of a rule, and similar transformations, do not work. Thus we obtain the equivalence of the following problems.

• Does the exponential time hierarchy for CSL collapse? That is, can all linear space-bounded automata be simulated by linear space-bounded automata with an additional universal exponential time bound?

• Does there exist a steady position valuation such that the corresponding class of weakly growing context-sensitive languages coincides with CSL?

• Does there exist a steady position valuation such that the corresponding class of weakly growing context-sensitive languages is closed under inverse homomorphism?

• Does there exist an unsteady position valuation such that the following holds: Every weakly growing context-sensitive grammar related to this position valuation can be transformed into an equivalent grammar in a normal form of order 2 that is weakly growing context-sensitive related to some position valuation?

2 Preliminaries

We will denote the set of positive and negative integers by ℤ, the set of

2-1

natural numbers by ℕ, the set ℕ \ {0} by ℕ^{+}, the set of rational numbers by ℚ, and the set of positive rational numbers by ℚ^{+}. Denote modified subtraction by · −.

We will denote a linear-bounded automaton by M = (Σ, Q, Γ, q_{0}, δ, F),

2-2

where Σ ⊆ Γ is the input alphabet, Q is the set of states, Γ is the working alphabet, q_{0} is the start state, δ: (Q×Γ)→(Q×Γ×{L, R}) is the transition function, and F is the set of accepting states. By uqv we denote a configuration of M, where uv is the content of the working tape, q is the actual

5 state, and the first symbol of v is being read. By K_{1} ⟼_{M}^{∗} K_{2} we denote that configuration K_{2} is reachable from configuration K_{1} by a computation of M (see, e.g., [HU79] for a detailed definition). The subscript M is sometimes omitted when it is obvious from the context. By M = (Σ, Q, q_{0}, δ, F) we denote a finite automaton, where the signature of δ is appropriately changed. Additionally, we use δ^{∗}: Q × Σ^{∗} → Q to denote the extension of δ to Q × Σ^{∗}.

A context-sensitive grammar (CSG) is a quadruple G = ⟨N, T, S, P ⟩,

2-3

where N and T are finite disjoint alphabets of nonterminal and terminal symbols, respectively, S ∈ N is the start symbol, and P is a finite set of rules (productions) of the form α → β with α, β ∈ (N ∪ T)^{∗}, where α contains at least one nonterminal symbol, and |α| ≤ |β| or (α → β) = (S → ε), and if (S → ε) ∈ P, S does not appear on the right-hand side of any rule. The corresponding language class is denoted by CSL.

If u, v ∈ (N ∪ T)^{∗} are sentential forms, we say u derives v in G =

2-4

⟨N, T, S, P ⟩, denoted by u ⟹ v, if there exist x, y, α, β ∈ (N ∪ T)^{∗} such

that u = xαy, v = xβy, and (α → β) ∈ P. Let ⟹^{∗} denote the reflexive and transitive closure of ⟹. Thus the language L(G) generated by a grammar

G is described by L(G) =^{def} { w ∈ T^{∗} : S ⟹_{G}^{∗} w }. For a language L ⊆ Σ^{∗}, the

transposition L^{T} of L is defined by L^{T} =^{def} { w : w^{T} ∈ L }, where w^{T} denotes the transposition of the string w ∈ Σ^{∗} inductively defined as follows: Define ε^{T} =^{def} ε, and for each v ∈ Σ^{∗} and each a ∈ Σ define (av)^{T} to be v^{T} a. Similarly, L_{1}·L_{2} =^{def} { w · v : w ∈ L_{1}, v ∈ L_{2} }, where w·v = wv is w concatenated with v.

Grammars with α ∈ N for each rule (α → β) ∈ P are called context-free.

2-5

The corresponding language class is denoted by CFL. Grammars with α ∈ N and β ∈ N · T ∪ T for each rule (α → β) ∈ P \ {(S → ε)} are called regular. The corresponding language class is denoted by REG.

By replacing the inequality in the definition of context-sensitive grammars

2-6

by a strict inequality, we obtain growing context-sensitive grammars (GCSG) that generate the growing context-sensitive languages (GCSL) (see [DW86], also [BL92], [Nie92]). The class GCSL is placed properly between CFL and CSL ([DW86], also see [Nie92]).

Instead of just counting the symbols appearing in a rule (as we did above),

2-7

we can assign each symbol a certain value (or weight). A grammar G = ⟨N, T, S, P ⟩ is called quasi-growing context-sensitive if it is context-sensitive

6 and there exists a function f: N ∪T →ℕ such that for each rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P:

∑_{i=1}^{n} f(α_{i}) < ∑_{i=1}^{m} f(β_{i}) or (α → β) = (S → ε)

The corresponding set of grammars is denoted by QGCSG. The function f is called a symbol valuation for G. By f|_{N} we denote the restriction of f to the set N.

If in the definition of QGCSGwe omit the requirement of context-sensitivity,

2-8

but keep the requirement that if (S → ε) ∈ P, S does not appear on the right-hand side of any rule, we obtain the quasi-growing grammars.

In [BL92] and [BL94] it was shown that both quasi-growing grammars

2-9

and quasi-growing context-sensitive grammars characterize the class of growing context-sensitive languages (also see [Nie92]). Instead of valuating only the symbols, we can also valuate their positions inside a rule. A position valuation is a function that is defined for an initial segment of the natural numbers. It must valuate at least one position. In the following we will refer to max{|α|, |β|} as the order of the rule α → β, and to ord(G) =^{def} max { max{|α|, |β|} : (α → β) ∈ P } as the order of G. Note that in the case of a context-sensitive grammar the order of G is equal to max { |β| : (α → β) ∈ P }. By “a normal form of order 2,” we mean a normal form such that every grammar in this normal form has order at most 2.

Definition 1 A position valuation is a function s: ℕ^{+} → ℕ^{+} with:

If s is defined for a j ∈ ℕ^{+}, then s is also defined for every i ∈ ℕ^{+} with i < j.

If s is defined for all i ∈ ℕ^{+}, we say s is an infinite position valuation—in the other case, s is a finite position valuation. We call each i ∈ ℕ^{+} where s(i) is defined a valuated position of s.

It is also possible to allow zero points for position valuations, but with the

2-10

techniques used to show our main results we get for each position valuation with zero points a characterization of CSL (see Theorem 8). We restrict ourselves to the most interesting position valuations which have at least two valuated positions.

Definition 2 Let s be a position valuation. A grammar G = ⟨N, T, S, P ⟩ is called weakly growing context-sensitive related to the position valuation s or also s-weakly growing context-sensitive, if the following hold:

7 (i) G is context-sensitive.

(ii) Let l be the order of G. Then s has at least l valuated positions.

(iii) There exists a function f: N∪T →ℕ such that for every rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P \ {(S → ε)} it holds that

∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i})  (∗)

Such a function f is called a symbol valuation for G. If the inequality (∗) above holds for a rule (α → β) ∈ P, we say α → β is s-weakly growing with f.

The sets of corresponding grammars and languages are denoted by WGCSG_{s} and WGCSL_{s}, respectively.

As we now valuate not only the symbols but also their positions inside a

2-11

rule, it is possible to interchange two symbols by a rule. This can be used to show that the language COPY =^{def} { ww : w ∈ {a, b}^{∗} } is weakly growing context-sensitive related to every nonconstant position valuation. To give an intuition of weakly growing context-sensitive grammars, we look at the following example closely.

Example 1 Consider the language COPY =^{def} { ww : w ∈ {a, b}^{∗} }. Let s be

Example 1-1

any position valuation with at least two valuated positions and s(1) < s(2). Define a grammar G = ⟨N, {a, b}, S, P ⟩ as follows:

Example 1-2

N =^{def} {S, S̃, A, A′, B, B′, (X, a), (X, b)}

and P contains the following rules:

S → ε  S → S̃
S̃ → AA′S̃  A′A → AA′  A′(X, a) → (X, a)a (X, a) → a
S̃ → BB′S̃  A′B → BA′  A′(X, b) → (X, a)b  (X, b) → b
S̃ → A(X, a)  B′A → AB′  B′(X, a) → (X, b)a  A → a
S̃ → B(X, b) B′B → BB′  B′(X, b) → (X, b)b  B → b

8 This grammar is context-sensitive, of order 2, and it generates the language COPY. Now we define f: N ∪ T → ℕ by:

f(S̃) =^{def} 1
f(S) =^{def} f(A) =^{def} f(B) =^{def} f((X, a)) =^{def} f((X, b)) =^{def} 2
f(A′) =^{def} f(B′) =^{def} 3
f(a) =^{def} f(b) =^{def} 3

With a simple calculation it can be seen that every rule of P is s-weakly growing with respect to this symbol valuation. Thus the grammar G is sweakly growing context-sensitive.

Example 1 □

As COPY ∉ GCSL [Bun93], we have WGCSL_{s} ⊈ GCSL for every non-

2-12

constant position valuation s. (The example above can be adapted easily for position valuations s with s(1) > s(2) and for those with a constant beginning part.)

Note that if we use classical context-sensitive grammars in the definition

2-13

of weakly growing context-sensitive grammars, we get a subclass of GCSG [Nie94]. Here the interesting question arises as to whether this class of grammars already characterizes the class GCSL. On the other hand, it can easily be seen that it is not possible to interchange two symbols back and forth in the same grammar; thus we know WGCSG_{s} ⊂ CSG for every position valuation s.

We now look briefly at some robustness properties of the definition of

2-14

weakly growing context-sensitive languages. As can easily be seen, the standard algorithm to delete chain rules (see, e.g., [Har78]) can be adapted for weakly growing context-sensitive grammars. The same applies to the standard algorithm to delete terminal symbols from the left-hand side of a rule. Thus we obtain:

Proposition 1 For every WGCSG related to a position valuation s, there

Proposition 1-1

exists an equivalent WGCSG_{s} without chain rules, even if there is only a symbol valuation known such that some chain rules are not strictly growing, i.e., cycling with chain rules can be deleted in such cases.

Furthermore, in a WGCSG_{s}, terminals can be forbidden on the left-hand

Proposition 1-2

side of rules without affecting the grammar’s inherent power.

9 In an inequality, the multiplication of both sides with the same positive

2-15

value does not affect its validity, and the following holds.

Proposition 2 For all k ∈ ℚ^{+}, the classes WGCSL_{k·s} are the same.

Thus, for each constant position valuation C, it holds that WGCSG_{C} =

2-16

QGCSG and consequently, WGCSL_{C} = GCSL.

The values on both sides of an inequality can not only be stretched, but

2-17

can also be shifted without affecting its validity, which leads to the following result.

Lemma 1 In Definition 2 (iii) it is sufficient to demand that there exists a function f: N ∪T →ℚ, i.e., with values in ℚ, that satisfies the inequality (∗).

Proof of Lemma 1 Let s be a position valuation and let G = ⟨N, T, S, P ⟩

Proof of Lemma 1-1

be a context-sensitive grammar where s has at least ord(G) valuated positions. Let f: N ∪ T → ℚ be a symbol valuation such that for every rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P not equal to (S → ε), it holds that

∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i})

Let \{a_{1}, …, a_{k}\} be the set of symbols N ∪ T and f(a_{i}) = \frac{p_{i}}{q_{i}} with p_{i} ∈ ℤ and q_{i} ∈ ℕ^{+} for i = 1, …, k. With an easy transformation we obtain a symbol valuation with symbols in ℕ: Let q =^{def} lcm(q_{1}, …, q_{k}) be the common denominator of all values and z =^{def} q · |min{0, p_{1}, …, p_{k}}| be the product of this common denominator with the absolute value of the smallest negative enumerator. Then by a linear transformation we obtain natural numbers: f′(a_{i}) =^{def} q · f(a_{i}) + z. The inequalities still apply, as the grammar has no length-decreasing rules.

Proof of Lemma 1 □

In a similar way, it can be seen that allowing values out of ℚ^{+} for position

2-18

valuations does not lead to any new language classes.

As we mentioned above, in the case of quasi-growing context-sensitive

2-19

grammars, if we omit the requirement of context-sensitivity, we obtain grammars that characterize the same language class [BL92]. In the case of weakly growing context-sensitive grammars, the effect is different: If in Definition 2 we leave out the requirement of context-sensitivity, we obtain the weakly

10 growing grammars, which already characterize the languages generated by nonrestricted grammars [Nie96], i.e., the class of recursively enumerable sets.

To lead to our main results we now introduce the two cases of steady and

2-20

unsteady position valuations.

Definition 3 A position valuation s: ℕ^{+}→ℕ^{+} is called steady if it coincides

Definition 3-1

with an exponential function on its domain, that is, if it can be written as

s(i) = s(1) · w(s)^{i−1}

where w(s) =^{def} \frac{s(2)}{s(1)}, so w(s) ∈ ℚ^{+}. This fraction, w(s), is called the growth factor of s.

In the other case, s is unsteady. Note that this is the case if and only if

Definition 3-2

s has at least three valuated positions, and if there exists a valuated position i ∈ ℕ^{+} of s, for which i − 1 and i + 1 are valuated, too, with:

s(i)^{2} ≠ s(i − 1) · s(i + 1)

In this case, we call such an i a blip of s, and the smallest such i we call the first blip of s.

Note that w(s) < 1 means s is monotone decreasing, and w(s) = 1 means

2-21

s is constant.

Definition 4 Let s be a position valuation. Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}, and let f be an appropriate symbol valuation for G. The growth rate of a rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P with respect to f is the difference ∑_{i=1}^{m} s(i) · f(β_{i})−∑_{i=1}^{n} s(i)·f(α_{i}) between the values on the right-hand and the left-hand sides of the rule. The growth rate of a derivation step u_{1} … u_{n} ⟹_{G} v_{1} … v_{m} with respect to f is the difference ∑_{i=1}^{m} s(i) · f(v_{i}) − ∑_{i=1}^{n} s(i) · f(u_{i}) between the values of v_{1} … v_{m} and u_{1} … u_{n}.

The relationship between the growth rate of a rule, the growth rate of a

2-22

derivation step, and the growth factor (in case of a steady position valuation) is investigated in Lemma 3 and Lemma 5. Nevertheless, we first look at general properties of weakly growing context-sensitive languages.

11

Buntrock and Niemann Weakly Growing CSGs §3.1

3 Closure Properties and Normal Form

The most important closure properties are the AFL properties. It turns

3-1

out that steadiness of a position valuation has no effect on these closure properties except for one (see Section 3.1). To the contrary, unsteadiness does affect the transformability of a weakly growing context-sensitive grammar into an equivalent grammar of the same type in normal form of order 2 (see Section 3.2). In Section 6 (Theorem 10), we will prove that the existence of one missing closure property (inverse homomorphism) for the weakly growing context-sensitive languages with steady position valuation is equivalent to the existence of a transformation into a normal form of order 2 for weakly growing context-sensitive grammars with unsteady position valuation.

3.1 Closure Properties

To get to know a new language class more closely, it is useful to learn some-

3.1-1

thing about its closure properties. Clearly, the closure under non-ε-free homomorphism of WGCSL_{s} yields the class of all recursively enumerable (r.e.) sets for every position valuation s, i.e., WGCSL_{s} is a basis for the class of r.e. sets (originally introduced by Raymond Smullyan in [Smu61]; see also [Bun96]). With standard arguments, we show the following.

Theorem 1 Let s be a position valuation with at least two valuated positions. WGCSL_{s} is closed under ε-free homomorphism, union, ε-free regular substitution, concatenation, and intersection with regular sets.

Proof of Theorem 1

For ε-free homomorphism: Let G = ⟨N, T, S, P ⟩ ∈ WGCSL_{s}, and let f

Proof of Theorem 1-1

be a symbol valuation for G. Let h: T → Δ be an ε-free homomorphism. A grammar G′ = ⟨N′, Δ, S, P′⟩ for h(L(G)) can be constructed by defin-

Proof of Theorem 1-2

ing N′ =^{def} N ∪ T and adding to P the rules (a → h(a)) for every a ∈ T to obtain P′. An appropriate symbol valuation can be found by extending f to Δ with f(u) = max { f(a) : a ∈ T } + 1 for u ∈ Δ.

For union: Let G_{1} = ⟨N_{1}, T_{1}, S_{1}, P_{1}⟩ and G_{2} = ⟨N_{2}, T_{2}, S_{2}, P_{2}⟩ be in

Proof of Theorem 1-3

WGCSL_{s}. Let f_{1} and f_{2} be appropriate symbol valuations for G_{1} and G_{2}, respectively. Wlog we can assume (N_{1} ∪T_{1})∩N_{2} = ∅ and N_{1} ∩(N_{2} ∪T_{2}) = ∅.

12 A grammar G = ⟨N, T_{1} ∪ T_{2}, S, P ⟩ for L(G_{1}) ∪ L(G_{2}) can be constructed by N = N_{1} ∪ N_{2} ∪ {S} and P = P_{1} ∪ P_{2} ∪ {(S → S_{1}), (S → S_{2})}. (Handling the case ε ∈ L(G_{1}) ∪ L(G_{2}) is standard.) An appropriate symbol valuation f is

defined by f|_{N_{1}∪T_{1}} =^{def} 2 · f_{1}, f|_{N_{2}∪T_{2}} =^{def} 2 · f_{2}, f(S) =^{def} 1.

For ε-free regular substitution: In fact, we can show that WGCSL_{s} is

Proof of Theorem 1-4

closed under ε-free WGCSL_{s} substitution. Then, closure under ε-free regular substitution follows, because every regular grammar is also weakly growing context-sensitive. Just use the symbol valuation f: N ∪ T → ℕ^{+} defined by f(A) =^{def} 1 for A ∈ N, f(a) =^{def} 2 for a ∈ T.

To show closure under ε-free WGCSL_{s} substitution, we consider G =

Proof of Theorem 1-5

⟨N, T, S, P ⟩ ∈ WGCSG_{s}, and for every a ∈ T let G_{a} = ⟨N_{a}, T_{a}, S_{a}, P_{a}⟩ ∈ WGCSG_{s}, where we can assume wlog that for every a and b in T with a ≠ b, it holds that (N_{a} ∪T_{a})∩N_{b} = ∅, and that terminals only appear on the righthand side of rules (Proposition 1). Let f and f_{a} for a ∈ T be appropriate symbol valuations, respectively. Let L_{a} =^{def} L(G_{a}).

Now we construct a grammar G′ = ⟨N′, T′, S, P′⟩ for the language

Proof of Theorem 1-6

L = { w : there exists v = a_{1} … a_{n} ∈ L with w ∈ L_{a_{1}} · . . . · L_{a_{n}} }

Let

N′ =^{def} N ∪ ⋃_{a∈T} N_{a}
T′ =^{def} ⋃_{a∈T} T_{a}
P′ =^{def} \begin{matrix}(P \ \{ (A → a) : A ∈ N, a ∈ T \}) ∪ \\ \{ A → S_{a} : (A → a) ∈ P \} ∪ ⋃_{a∈T} P_{a} \end{matrix}

What happens is that every original terminal is taken as a start symbol for the grammar of the substituting language. The function

f′: N ∪ ⋃_{a∈T}(N_{a} ∪ T_{a}) → ℕ^{+}

defined by

f′|_{N} =^{def} f
f′|_{N_{a}∪T_{a}} =^{def} max { f(b) : b ∈ T } · f_{a} for a ∈ T

is an appropriate symbol valuation for G′.

13 For concatenation: Let G_{1} = ⟨N_{1}, T_{1}, S_{1}, P_{1}⟩ and G_{2} = ⟨N_{2}, T_{2}, S_{2}, P_{2}⟩

Proof of Theorem 1-7

be in WGCSL_{s}. Let f_{1} and f_{2} be appropriate symbol valuations for G_{1} and G_{2}, respectively.

Wlog we can assume (N_{1} ∪ T_{1}) ∩ N_{2} = ∅ and N_{1} ∩ (N_{2} ∪ T_{2}) = ∅, and

Proof of Theorem 1-8

that terminals only appear on the right-hand side of rules (Proposition 1). A grammar G = ⟨N, T_{1} ∪ T_{2}, S, P ⟩ for L(G_{1}) · L(G_{2}) can be constructed by defining N =^{def} N_{1} ∪ N_{2} ∪ {S} and P =^{def} P_{1} ∪ P_{2} ∪ {(S → S_{1}S_{2})}. (Handling the cases ε ∈ L(G_{1}) and ε ∈ L(G_{2})is standard.) An appropriate symbol valuation f is found by joining f_{1} and f_{2} and defining f(S) =^{def} 1.

For intersection with regular sets: Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s},

Proof of Theorem 1-9

let L be a regular set, and let M = (Q, Σ, q_{0}, δ, F) be a deterministic finite automaton that accepts L.

By Proposition 1, we can assume that there appear only nonterminals in

Proof of Theorem 1-10

the left-hand sides of the rules in G. A grammar G′ = ⟨N′, T ∩ Σ, S′, P′⟩ for L ∩ L(G) is constructed as follows: N′ =^{def} { (p, A, q) : p, q ∈ Q, A ∈ N } ∪ {S′} (so the nonterminals are triples), and P contains the following rules (for every A_{1}, …, A_{n}, B_{1}, …, B_{m} ∈ N, u_{0}, …, u_{m+1}, w ∈ (Σ ∩ T)^{∗}, and q_{1}, …, q_{n+1}, p_{1}, …, p_{m}, p′_{1}, …, p′_{m} ∈ Q):

S′ →w if (S → w) ∈ P and w ∈ L
S′ →u_{0}(p_{1}, B_{1}, p′_{1})u_{1}(p_{2}, B_{2}, p′_{2}) … u_{m−1}(p_{m}, B_{m}, p′_{m})u_{m}
if (S′ → u_{0}B_{1}u_{1}B_{2} … u_{m−1}B_{m}u_{m}) ∈ P and
δ^{∗}(q_{0}, u_{0}) = p_{1} and
δ^{∗}(p′_{i}, u_{i}) = p_{i+1} for i = 1, …, m − 1 and
δ^{∗}(p′_{m}, u_{m}) ∈ F
(q_{1}, A_{1}, q_{2})(q_{2}, A_{2}, q_{3}) … (q_{n}, A_{n}, q_{n+1}) →
u_{1}(p_{1}, B_{1}, p′_{1})u_{2}(p_{2}, B_{2}, p′_{2}) … u_{m}(p_{m}, B_{m}, p′_{m})u_{m+1}
if (A_{1}A_{2} … A_{n} → u_{1}B_{1}u_{2}B_{2} … u_{m}B_{m−1}u_{m+1}) ∈ P and
δ^{∗}(q_{1}, u_{1}) = p_{1} and
δ^{∗}(p′_{i}, u_{i+1}) = p_{i+1} for i = 1, …, m − 1 and
δ^{∗}(p′_{m}, u_{m+1}) = q_{n+1}
(q_{1}, A_{1}, q_{2})(q_{2}, A_{2}, q_{3}) … (q_{n}, A_{n}, q_{n+1}) → w
if (A_{1}A_{2} … A_{n} → w) ∈ P and δ^{∗}(q_{1}, w) = q_{n+1}

14 (This construction is due to [GGH69]. Matthias Jantzen uses this to show the same result for GCSL [Jan79].)

The function f: N → ℕ^{+} defined by

Proof of Theorem 1-11

f′((p, A, q)) =^{def} f(A)  for p, q ∈ Q, A ∈ N
f′(S′) =^{def} f(S)
f′(a) =^{def} f(a)  for a ∈ T

is an appropriate symbol valuation for G′.

Proof of Theorem 1 □

We have proved the AFL properties (except the closure under inverse

3.1-2

homomorphism). Now we show the closure under transposition. We will use this result in the proof of Theorem 4, where we show an important property concerning steady position valuations.

Theorem 2 Let s be a nonconstant position valuation. Then WGCSL_{s} is closed under transposition.

Proof of Theorem 2 We sketch the idea for the case s(1) < s(2).

Proof of Theorem 2-1

For a grammar G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}, a grammar G̃ = ⟨Ñ, T, S̃, P̃⟩

Proof of Theorem 2-2

is constructed as follows:

Ñ =^{def} N ∪ {S̃} ∪ { a′ : a ∈ T } ∪ { X̌ : X ∈ N } ∪ { ǎ : a ∈ T }

where the rules in P̃ accomplish the following:

First, for a word w = w_{1} … w_{n} ∈ L, the sentential form w̌_{1}w′_{2} … w′_{n} is generated (for this, appropriate copies of the rules in P are used). Then this sentential form is transformed with rules of the form

ǎb′ → b̌a
ab′ → b′a
ǎ → a

into the word w_{n} … w_{1}.

15 Clearly L(G̃) = L(G)^{T}. Out of a symbol valuation f for G an appropriate symbol valuation for G̃ can be constructed in the following way.

Define f̃: Ñ → ℕ^{+} by

Proof of Theorem 2-3

f̃(X) =^{def} f(X) for X ∈ N  f̃(X̌) =^{def} f(X) for X ∈ N
f̃(a′) =^{def} f(a) for a ∈ T  f̃(ǎ) =^{def} f(a) for a ∈ T
f̃(S̃) =^{def} f(S)  f̃(a) =^{def} max { f(a) : a ∈ T } + 1

For a symbol valuation s with s(1) > s(2), the proof works analogously.

Proof of Theorem 2-4

For the case of a nonconstant position valuation with s(1) = s(2), this idea can be adapted by shifting the “mirror point” X̌ and treating the borders appropriately.

Proof of Theorem 2 □

To show that WGCSL_{s} is an AFL for a certain position valuation s, we

3.1-3

would have to show that WGCSL_{s} is closed under inverse homomorphism (or under k-bounded homomorphism because of Theorem 1, and from [GGH69] we know that both closure properties are equivalent under the assumption that the closure properties named in Theorem 1 apply).

For steady position valuations, this problem is equivalent to the prob-

3.1-4

lem of whether all linear space-bounded automata can be simulated by linear space-bounded automata with an additional universal exponential time bound (see Theorem 10). The reason for this equivalence lies in the fact that for every position valuation, the closure under inverse homomorphisms of WGCSL_{s} equals CSL (see Theorems 5 and 9).

3.2 Normal Form

In Section 2 we introduced the two cases of steady and unsteady position

3.2-1

valuations. Now we work out what we can say about the transformability of corresponding weakly growing context-sensitive grammars into a normal form of order 2.

For every steady position valuation s, each grammar in WGCSG_{s} can be

3.2-2

transformed into a normal form of order 2. We will use Cremers normal form [Cre73]. Compared with all other normal forms of order 2, the advantage of Cremers normal form lies in its minimal number of different types of rules. Moreover, with the probably more popular normal form proposed by Kuroda,

16 we can only describe classical context-sensitive grammars, which leads here to a language class contained in GCSL, as we mentioned in Section 2.

Definition 5 ([Cre73]) A context-sensitive grammar G = ⟨N, T, S, P ⟩ is in Cremers normal form if every rule in P is of one of the forms AB → CD, A → CD, or A → a, where A, B, C, D ∈ N, a ∈ T.

At first, we adapt the obvious algorithm to reduce the order of a gram-

3.2-3

mar.

Lemma 2 Let s be a steady position valuation. Then for every grammar G ∈ WGCSG_{s} of order l ≥ 3, there exists an equivalent grammar G′ ∈ WGCSG_{s} of order l − 1.

Proof of Lemma 2 Let s: ℕ^{+} → ℕ^{+} be a steady position valuation with

Proof of Lemma 2-1

at least three valuated positions (in the other case there is nothing to show). Define s′: ℕ^{+} → ℕ^{+} by s′(i) =^{def} s(i + 1) for all i ∈ ℕ^{+}, that is, if s(i + 1) is undefined, so is s′(i). Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} be of order l ≥ 3, let f: N ∪ T → ℕ be a symbol valuation for G.

We now construct a grammar G′ = ⟨N′, T, S′, P′⟩ and a symbol valuation

Proof of Lemma 2-2

f′: N′ ∪ T → ℚ by the following algorithm:

1. N′ := N, P′ := ∅.

2. f′(A) := f(A) for every A ∈ N, f′(a) := f(a) for every a ∈ T.

3. For every rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P, execute the following:

4. If m ≤ 2, then P′ := P′ ∪ {(α_{1} … α_{n} → β_{1} … β_{m})}.

5. If 3 ≤ m ≤ l, then let X be a new nonterminal symbol, X ∉ N′.

6. Define the rules:

(R1)  α_{1}α_{2} → β_{1}X
(R2) Xα_{3} … α_{n} → β_{2} … β_{m}

Here n = 2, which means α_{3} … α_{n} = ε, or n = 1, which means additionally α_{2} = ε is possible.

7. P′ := P′ ∪ {(R1), (R2)}.

8. f′(X) := \frac{s(1)}{s(2)} · f(α_{1}) + f(α_{2}) − \frac{s(1)}{s(2)} · f(β_{1}) + \frac{1}{2·s(2)}

17

It holds that L(G′) = L(G). As G is context-sensitive, so is G′. By calculation and Lemma 1 it can be shown that G′ ∈ WGCSG_{s′}. By Proposition 2 this implies G′ ∈ WGCSG_{s} (since s(i) = w(s) · s′(i) for every i ∈ ℕ^{+}).

Proof of Lemma 2 □

For unsteady position valuations, this algorithm and similar ones do not

3.2-4

work. This can be checked looking at the following interesting example.

Example 2 Let s = id, i.e., s(i) = i for every i ∈ ℕ^{+}. Let α_{1}α_{2}α_{3} → β_{1}β_{2}β_{3} be a rule, and let f(α_{1}) = 1, f(α_{2}) = 1, f(α_{3}) = 3, f(β_{1}) = 1, f(β_{2}) = 5, and f(β_{3}) = 1. Then the rule is id-weakly growing with f, and in the rules α_{1}α_{2} → β_{1}X and Xα_{3} → β_{2}β_{3}, the symbol X cannot be valuated appropriately.

Example 2 □

Lemma 2 can be applied step by step; thus together with Proposition 1

3.2-5

we obtain the following.

Theorem 3 Let s be a steady position valuation. For every grammar G ∈ WGCSG_{s}, there exists an equivalent grammar G′ ∈ WGCSG_{s} in Cremers normal form.

Thus for a steady position valuation s, the class WGCSL_{s} is characterized

3.2-6

by the growth factor w(s) (this follows from Theorem 3 and Proposition 2). We introduce the following notation:

WGCSL_{w(s)} =^{def} WGCSL_{s}

When we treat steady position valuations, we can assume wlog that s is

3.2-7

an exponential function, or, if more convenient, that s is a position valuation with only two valuated positions. Additionally, we can assume that it is monotone increasing.

Theorem 4 Let s be a steady position valuation. Then

WGCSL_{w(s)} = WGCSL_{\frac{1}{w(s)}}

That is, having a position valuation s, we can assume wlog it is monotone increasing.

18 Proof of Theorem 4 Let s be a steady position valuation, let G =

Proof of Theorem 4-1

⟨N, T, S, P ⟩ ∈ WGCSL_{s} = WGCSL_{\frac{s(2)}{s(1)}} be in Cremers normal form (The-

orem 3), and let f be a symbol valuation for G. We define a grammar G′ = ⟨N, T, S, P′⟩, where P′ contains the transposed version of every rule in P. Clearly, G′ is context-sensitive and L(G′) = L(G)^{T}. Define a position valuation s′ by s′(1) =^{def} s(2), s′(2) =^{def} s(1). If G′ ∈ WGCSG_{s′} = WGCSG_{\frac{s(1)}{s(2)}} , then the claim follows from Theorem 2.

The transposed versions of the length-preserving rules clearly are s′-

Proof of Theorem 4-2

weakly growing with respect to f. Now we look at the expanding rules and define an appropriate symbol valuation f′ for G′.

Consider a rule (A → BC) ∈ P. Then s(1)·f(A) < s(1)·f(B)+s(2)·f(C).

Proof of Theorem 4-3

If s(2)·f′(A) < s(2)·f′(C)+s(1)·f′(B) holds, the rule A → CB is s′-weakly growing with respect to f′. We attach an additional weight piece to B in order to fulfill this inequality, that is, we define f′(B) =^{def} f(B) + b where b =^{def} \frac{s(2)−s(1)}{s(1)} · m with m ≥ f(A). Attaching this same weight piece to A and C does not affect the validity of the given inequality.

We define m =^{def} max { f(A) : A ∈ N }, and define f′: N ∪ T → ℚ by

Proof of Theorem 4-4

f′(X) =^{def} f(X) + \frac{s(2) − s(1)}{s(1)} · m for X ∈ N ∪ T

Then every transposed version of an expanding rule in P is s′-weakly growing with respect to f′. As f′ differs from f only by a constant addend, the transposed versions of the length-preserving rules in P are s′-weakly growing with respect to f′ also. Thus G′ ∈ WGCSG_{s′} follows from Lemma 1.

Proof of Theorem 4 □

4 The Unsteady Position Valuation

In this section it is shown that WGCSL_{s} = CSL for every unsteady position

4-1

valuation s. The only inclusion we have to show is CSL ⊆ WGCSL_{s}. It is well known that linear-bounded automata characterize the context-

4-2

sensitive languages [Kur64]. This will be used extensively when we show the claim mentioned above. There the following technique for simulating a linearbounded automaton by a context-sensitive grammar is adapted (see, e.g., [Har78]): We use a linear-bounded automaton that has a single tape, writes

19

...  …^{}sentential form: LBA:  state q^{[\begin{matrix}i \\ w \end{matrix}]} o..r. \begin{matrix}[ & {n \atop k} & ] \\ [ & \begin{matrix}p \\ - \\ q \end{matrix} & ] \\ [ & {u \atop t} & ] \end{matrix}a. .p. ^{[\begin{matrix}t \\ e \end{matrix}]}

Figure 1: Tape and sentential form (sketch)

only on the tape cells marked by the input, and makes no null moves. This can be done without loss of generality (see, e.g., [Tur36], [Har78], [HU79]). Each configuration is represented by a certain sentential form (see Figure 1). We work on three tracks, as follows. On the first track, we hold the input, on the second track we always have the actual contents of the working tape, and on the third track we have the actual state, put down exactly below the symbol the linear-bounded automaton is actually reading. This sentential form is generated with the initial configuration with an arbitrary input, then M is simulated step by step, and if M accepts, the triples are transformed into the contents of their first component, which then become terminal symbols.

To simulate a context-sensitive grammar by a linear-bounded automaton,

4-3

we just follow a derivation step by step and compare the derived word with the input afterwards.

As we mentioned earlier, for every unsteady position valuation s,

4-4

WGCSL_{s} = CSL. To prove this, we use that every unsteady position valuation s has a blip (see Definition 3). We distinguish four cases for an unsteady position valuation s, where j is the first blip:

(i) s(j − 1) > s(j) and s(j) < s(j + 1), that is, j is a “valley blip,”

(ii) s(j − 1) < s(j) and s(j) > s(j + 1), that is, j is a “peak blip,”

(iii) s is monotone increasing on an initial part up to the position j +1, and

(iv) s is monotone decreasing on an initial part up to the position j + 1.

Every unsteady position valuation corresponds to one of the cases above. In each case we introduce for a linear-bounded automaton a way of construct-

20

[figure: rule in P:; LBA:; \begin{aligned}[ & p & ] \\ [ & ] \\ & [ & ] \end{aligned}; state p; state q; [q]_{[ ]}^{[ ]}; e.g., movement; to the left; s:]

Figure 2: Simulation in the first case (sketch)

ing an s-weakly growing context-sensitive grammar following the algorithm mentioned above.

For the first case (i): Given a linear bounded automaton M =

4-5

(Σ, Q, Γ, q_{0}, δ, F), we construct the simulating grammar G = ⟨N, T, S, P ⟩ as follows. N consists of triples, where the first component contains an element of Σ, the second an element of Γ, and the third is empty or contains a state. Additionally, N contains marked copies of those symbols for the righthand and the left-hand borders. The idea is to valuate (by an appropriately defined symbol valuation) all triples without state with the same value, and the triples containing a state with a greater value.

The “valley blip” in the position valuation is then used as follows. In a

4-6

rule that simulates a step of M, the state “moves” following the move of the automaton’s head. Thus, the additional weight induced to a nonterminal by the state also “moves,” and by an appropriate left-hand context (that is, by j − 2 preceding nonterminals for moving to the left, j − 1 for moving to the right, where the position j is the “valley blip”), the rule is constructed so that on the left-hand side the state is positioned exactly on that blip. In Figure 2 this is illustrated. Thus, for (p, y, R) ∈ δ(q, x), the rules

α[\begin{matrix}a \\ x \\ q \end{matrix}][\begin{matrix}b \\ z \end{matrix}]→ α[\begin{matrix}a \\ y \end{matrix}][\begin{matrix}b \\ z \\ p \end{matrix}]

for α ∈ N^{j−1} (nonstate symbols only), a, b ∈ Σ, z ∈ Γ are in P; for (p, y, L) ∈ δ(q, x) the rules

21

α[\begin{matrix}a \\ z \end{matrix}][\begin{matrix}b \\ x \\ q \end{matrix}]→ α[\begin{matrix}a \\ z \\ p \end{matrix}][\begin{matrix}b \\ y \end{matrix}]

for α ∈ N^{j−2} (nonstate symbols only), a, b ∈ Σ, z ∈ Γ are in P.

Since the positions to the right and to the left of the “valley blip” j are

4-7

both valuated higher than the blip itself, these rules become s-weakly growing with a symbol valuation according to the conditions we stated above. To continue working, that is, to apply such a rule on a sentential form, there must exist at least j − 1 symbols in the sentential form to the left of the state.

Therefore, at the left-hand border we condense several steps: For w, w′ ∈

4-8

Σ^{j−1}, w = w_{1} … w_{j−1}, w′ = w′_{1} … w′_{j−1}, x, y ∈ Σ,q, p ∈ Q with wqx ⟼_{M}^{∗} w′yp

the rules

[\begin{matrix}a_{1} \\ w_{1} \\ ♡ \end{matrix}][\begin{matrix}a_{2} \\ w_{2} \end{matrix}]…[\begin{matrix}a_{j−1} \\ w_{j−1} \end{matrix}][\begin{matrix}a \\ x \\ q \end{matrix}][\begin{matrix}b \\ z \end{matrix}]→[\begin{matrix}a_{1} \\ w′_{1} \\ ♡ \end{matrix}][\begin{matrix}a_{2} \\ w′_{2} \end{matrix}]…[\begin{matrix}a_{j−1} \\ w′_{j−1} \end{matrix}][\begin{matrix}a \\ y \end{matrix}][\begin{matrix}b \\ z \\ p \end{matrix}]

for a_{1} … a_{j−1}, a, b ∈ Σ, z ∈ Γ are in P. (The ♡ here serves as a mark for the left-hand border.)

4-9 To build an initial sentential form for the input a_{1} … a_{j} … a_{n}, we use an analogous condensation of steps: For q_{0}a_{1} … a_{j−1} ⟼_{M}^{∗} a′_{1} … a′_{j−1}p_{0} we build

[\begin{matrix}a_{1} \\ a′_{1} \\ ♡ \end{matrix}][\begin{matrix}a_{2} \\ a′_{2} \end{matrix}]…[\begin{matrix}a_{j−1} \\ a′_{j−1} \end{matrix}][\begin{matrix}a_{j} \\ a_{j} \\ p_{0} \end{matrix}][\begin{matrix}a_{j+1} \\ a_{j+1} \end{matrix}]…[\begin{matrix}a_{n} \\ a_{n} \\ ♢ \end{matrix}]

(where ♡ serves to mark the left-hand, and ♢ to mark the right-hand borders).

Triples containing an accepting state are transformed into their first com-

4-10

ponent, which then become terminal symbols. Every triple near a terminal is transformed in this way, too. For a detailed and explicit construction of the grammar see [Nie94].

For the second case (ii): In the case of a “peak blip” we can use the same

4-11

algorithm as we used in the first case. In fact, we can use the same grammar. We just have to redefine the symbol valuation so that the nonterminals representing simple tape cells are valuated higher than the nonterminals containing a state.

22

[figure: LBA:; \begin{matrix}[ & p^{L} & ] \\ [ & ⋆ & ] \end{matrix}; state q; [q^{R}]^{[ ]}; reversal; state p; rule in P:]

In the sentential form, the following should happen:

[ ]…[ ][p^{L}][⋆][ ]…[ ][swallower]

⟶_{passing} [ ]…[ ][p^{L}][ ]…[ ][⋆][swallower]

⟶_{swallowing} [ ]…[ ][p^{L}][ ]…[ ][ ][swallower]

Figure 3: Simulation with swallower

For the third case (iii): Concerning a monotone increasing position val-

4-12

uation (up to the position j + 1), we relate the state with a greater value (than the simple tape cells) for moving to the right and with a lower value for moving to the left. To do this, we mark the state with the direction it moved the last time. With a reversal (change of direction of the move) this value must be changed. It is no problem in a weakly growing grammar to change from a lower to a greater value. But going the other way, we will use a trick to erase the “surplus weight.” First, it is encoded in a certain symbol (we will use a star ⋆) and laid down beside the point of reversal. From there it is passed through to the right to be swallowed. This is illustrated in Figure 3. It is no problem to let the “surplus weight” (encoded in the star ⋆) pass through to the right.

23 We now introduce a swallower. Informally, a swallower consists of a string

4-13

θ together with some rules that can be integrated into a given s-weakly growing context-sensitive grammar G so that every sentential form wY θ can be transformed into wXθ, where the nonterminal X is valuated lower than the nonterminal Y by a symbol valuation for G.

Definition 6 Let s be an unsteady position valuation which is monotone increasing on an initial part up to a position after its first blip, and let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Define a swallower for s and G (also called an s-swallower for G) to be a quintuple S_{s,G} = (N_{1}, N_{2}, N_{swallow}, θ, P_{swallow}) such that:

• The components of the quintuple are

– N_{1} and N_{2} are nonempty subsets of N,

– N_{swallow} is a set of nonterminals (not necessarily a subset of N),

– θ ∈ N_{swallow}^{∗} is a string, and

– P_{swallow} is a set of rules of the form α → β where α, β ∈ (N ∪ N_{swallow} ∪ T)^{∗}. Every rule in P_{swallow} is context-sensitive.

• There exists a symbol valuation f: N ∪ N_{swallow} ∪ T → ℕ with

– f is a symbol valuation for G, i.e., every rule in P is s-weakly growing with f,

– every rule in P_{swallow} is s-weakly growing with f, and

– for every X ∈ N_{1}, Y ∈ N_{2}, it holds that f(X) < f(Y).

• There exists an l ∈ ℕ such that for every w ∈ (N ∪ T)^{∗} with |w| ≥ l and for every X ∈ N_{1}, Y ∈ N_{2}, it holds that wY θ ⟹_{P_{swallow}}^{∗} wXθ.

If N_{swallow} ⊆ N and P_{swallow} ⊆ P, we also call S_{s,G} an s-swallower in G. If s and G are clear from the context, the subscripts are dropped.

To illustrate how a swallower can be built, we give an example first.

4-14

Example 3 Take the unsteady position valuation id defined by id(i) =^{def} i for

Example 3-1

every i ∈ ℕ^{+}.

Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{id} with X, Y ∈ N, and let f be a symbol

Example 3-2

valuation for G with f(X) = 1, f(Y) = 2.

24 Define S = (N_{1}, N_{2}, N_{swallow}, θ, P_{swallow}) with N_{1} =^{def} {X}, N_{2} =^{def} {Y },

Example 3-3

N_{swallow} =^{def} {M, [⋆], A, B, V }, θ =^{def} MAV, and a set of rules P_{swallow} comprising

(R1) Y M → X[⋆] (R2) [⋆]AV → MBA (R3) BA → AV

Using these rules out of P_{swallow}, the following derivation steps are possible:

Y MAV ⟹_{R1} X[⋆]AV ⟹_{R2} XMBA ⟹_{R3} XMAV

Now extend the symbol valuation f to N_{swallow} as follows:

f(M) =^{def} 1 f([⋆]) =^{def} 2
f(A) =^{def} 1  f(B) =^{def} 8 f(V) =^{def} 5

In this way we obtain the following valuations for the rules in P_{swallow}:

for (R1):  1 · 2 + 2 · 1 = 4 < 5 = 1 · 1 + 2 · 2
for (R2): 1 · 2 + 2 · 1 + 3 · 5 = 19 < 20 = 1 · 1 + 2 · 8 + 3 · 1
for (R3):  1 · 8 + 2 · 1 = 10 < 11 = 1 · 1 + 2 · 5

Thus, these rules are id-weakly growing with f.

In the construction of these rules, we exploit that with the position valu-

Example 3-4

ation id, a value moving from the first to the second position can be divided in half (this happens in (R2) with the “value” 1 of the star), and moving from the third to the second position it must be multiplied only with one and a half (this happens in (R2) with the “value” f(V) − f(A) = 4). Here the values are chosen in a way that dividing the value collected in B by 2 (that is ⌈\frac{1}{2} · 1⌉ + \frac{3}{2} · 4 = 7 = f(B) − f(A) and happens in (R3)) the situation of the beginning is restored.

In this way, the sentential form MAV together with the set of rules

Example 3-5

P_{swallow} swallows a value encoded in the star, and S is an id-swallower in G.

Example 3 □

Now we turn to the construction of a swallower for each unsteady position

4-15

valuation that is monotone increasing at least up to a position after its first blip.

25 Lemma 3 Let s be an unsteady position valuation which is monotone in-

4-16

creasing on a beginning part up to a position after the first blip, and let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Let f be a symbol valuation for G that valuates at least two symbols out of N differently. Then there exists an s-swallower for G.

Note that this lemma also means that concerning an unsteady position

4-17

valuation, a positive growth rate of a rule does not necessarily mean a positive growth rate of the corresponding derivation step.

Proof of Lemma 3 We just introduce the construction of the swallower

Proof of Lemma 3-1

and how the symbol valuation f can be extended to become an appropriate symbol valuation for the swallower S = (N_{1}, N_{2}, N_{swallow}, θ, P_{swallow}) as well.

Let j be the first blip of s. Let N_{1} and N_{2} be nonempty subsets of N with

Proof of Lemma 3-2

f(X) < f(Y) for every X ∈ N_{1}, Y ∈ N_{2}. Define N_{swallow} =^{def} {M, [⋆], A, B, V },

θ =^{def} MAV, let

l =^{def} \{ \begin{matrix}j − 1 & if s(j − 1) = s(j) \\ j − 2 & if s(j − 1) < s(j) \end{matrix}

and define P_{swallow} as follows:

R_{1} =^{def} { αY M → αX[⋆] : α ∈ (N ∪ T)^{l}, Y ∈ N_{2},, X ∈ N_{1} }
R_{2} =^{def} { α[⋆]AV → αMBA : α ∈ (N ∪ T)^{j−2} }
R_{3} =^{def} { αBA → αAV : α ∈ (N ∪ T)^{j · −3} · {M, ε}, |α| = j − 2 }
P_{swallow} =^{def} R_{1} ∪ R_{2} ∪ R_{3}

Note that the lengths of α in R_{2} and R_{3} are different, and that M appears in R_{3} iff j > 2.

Now we extend the symbol valuation f to N_{swallow} with values in ℚ as

Proof of Lemma 3-3

follows, where μ =^{def} max { f(Y) − f(X) : X ∈ N_{1}, Y ∈ N_{2} }:

f(M) =^{def} 1  f([⋆]) =^{def} 1 + μ  f(A) =^{def} 1
f(B) =^{def} \frac{1}{s(j)^{2} − s(j − 1) · s(j + 1)} · (s(j − 1) · s(j) · μ + s(j) + s(j + 1)) + 1
f(V) =^{def} \frac{1}{s(j)^{2} − s(j − 1) · s(j + 1)} · ((s(j − 1))^{2} · μ + s(j − 1) + s(j)) + 1

It can be checked arithmetically that the rules in P_{swallow} all are s-weakly

Proof of Lemma 3-4

growing with f. (To check R_{2} and R_{3}, it is helpful first to compute s(j) · 26 f(B) − s(j + 1) · f(V) and s(j) · f(V) − s(j − 1) · f(B), respectively.) As we have seen in Lemma 1, f can be transformed into a symbol valuation with values in ℕ^{+}.

Thus f is now a symbol valuation for the swallower as well. Let w ∈

Proof of Lemma 3-5

(N ∪ T)^{∗} with |w| ≥ l, and let X ∈ N_{1}, Y ∈ N_{2}. With θ = MAV the following derivation steps are possible:

wY θ = wY MAV ⟹_{R_{1}} wX[⋆]AV ⟹_{R_{2}} wXMBA ⟹_{R_{3}} wXMAV = wXθ

Proof of Lemma 3 □

So we can integrate a swallower into an s-weakly growing context-sensitive

4-18

grammar, where s is unsteady and monotone increasing on a beginning part up to a position after the first blip j, that simulates a linear bounded automaton in the way we mentioned at the beginning of this section. To get a sentential form that is not too long, we condense every two cells of the linear bounded automaton (see linear tape compression in the literature).

When the linear bounded automaton accepts, the sentential form is trans-

4-19

formed into terminals and expanded at the same time. Together with the expansion the swallower disappears. If s on a beginning part is constant, we have the same conditions for border-handling during the simulation as we had in the first and the second cases.

For the fourth case (iv): Concerning an unsteady position valuation that

4-20

is monotone decreasing on a beginning part up to a position after the first blip j, the simulation of a linear bounded automaton works quite analogously. For a move to the right, the state is related to a lower value, for a move to the left the state is related to a higher value than the simple tape cells. This means the “surplus weight” is generated in a left-right reversal, and is passed through to the left, where it is swallowed. The swallower is also constructed in a similar way: The string and the parts of the rules that change are transposed, a dummy symbol is added to the left-hand context of the rules in R_{3}, and the left-hand context of every rule is replaced by dummy symbols. Such a swallower can be integrated in an analogous way to the one introduced above, and thus the claim can be shown for this case, too.

Conclusion: Since in all cases (i) through (iv) we can construct an appro-

4-21

Buntrock and Niemann Weakly Growing CSGs §5.1.1

priate weakly growing context-sensitive grammar, we have the following: 27 Theorem 5 For every unsteady position valuation s, it holds that

WGCSL_{s} = CSL

For a more detailed description, see [Nie94].

4-22

5 The Steady Position Valuation

We intend to find a characterization of a weakly growing context-sensitive

5-1

language class related to a steady position valuation by linear bounded automata with a certain time bound. We approach this goal in three steps: First, we estimate the length of a derivation in a given weakly growing context-sensitive grammar related to a steady position valuation, and realize an efficient simulation (Section 5.1). Second, we introduce an instrument that will help in the simulation of linear bounded automata by weakly growing context-sensitive grammars related to a steady position valuation. This instrument is a new kind of counter: grammars that count, where the counted items in fact are weight pieces (Section 5.2). With these preparations the simulation will be done easily (Section 5.3). Note, however, that with our methods it is not possible to show a one-to-one correspondence, due to the counter’s capacity.

5.1 Efficient Simulation of a Grammar

5.1.1 Connected Grammars

In a simulation of a grammar with a linear bounded automaton, the automa-

5.1.1-1

ton can follow the derivation step by step, if it is connected (see Definition 7), while in a nonconnected grammar, in every step it must move to the position of replacement first. To gain an effective simulation, we will make use of the property to be connected (see [Gla64], [Boo69], [Bun93]).

Definition 7 Let G = ⟨N, T, S, P ⟩ be a grammar. Let w_{0} = S ⟹ w_{1} ⟹ … ⟹ w_{t} be a derivation in G, and let (α_{i} → β_{i}) ∈ P be the rule applied in the step w_{i} ⟹ w_{i+1}. The derivation is connected if for each i = 1, 2, …, t−1 the substrings α_{i} and β_{i−1} of w_{i} have a nonempty overlap. The grammar G is connected if each derivation w_{0} ⟹^{∗} w_{t} with w_{0} = S is connected.

28 Gladkii showed that every grammar (of both general and context-sensitive

5.1.1-2

types) can be transformed into an equivalent grammar of the same type that is connected [Gla64]. Using Book’s proof in [Boo69], in [Bun93] it was shown that this also is true for quasi-growing context-sensitive grammars. Here we will show that the same is true for s-weakly growing context-sensitive grammars, for every steady position valuation s.

Book’s proof carries over easily when we use Cremers normal form (Theo-

5.1.1-3

rem 3), and we can assume that the position valuation is monotone increasing (see Theorem 4).

Lemma 4 Let s be a steady, strictly monotone increasing position valuation. Then for each grammar G ∈ WGCSG_{s} in Cremers normal form, there exists a connected grammar G′ ∈ W GCSG_{s} with L(G′) = L(G). Additionally, the length of a derivation for a word w in G′ is at most doubled compared to the length in G.

Proof of Lemma 4 Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} in Cremers normal

Proof of Lemma 4-1

form. Let f be a symbol valuation for G.

Define a grammar G′ = ⟨N′, T, Ŝ, P′⟩ by N′ =^{def} N ∪ { Â : A ∈ N }, that

Proof of Lemma 4-2

is, the old set of nonterminals together with a set of new nonterminals in one-to-one correspondence with the old, and the following rules:

P_{1} =^{def} { ÂB → ĈD, AB̂ → ĈD, AB̂ → CD̂ : A, B, C, D ∈ N, (AB → CD) ∈ P }
P_{2} =^{def} { Â → ĈD, Â → CD̂ : A, C, D ∈ N, (A → CD) ∈ P }
P_{3} =^{def} { Â → a, ÂX → aX̂ : A, X ∈ N, a ∈ T, (A → a) ∈ P }
P_{4} =^{def} { ÂB → AB̂ : A, B ∈ N }
P′ =^{def} P_{1} ∪ P_{2} ∪ P_{3} ∪ P_{4}

Following an argument given in [Boo69] we see that L(G′) = L(G), and G′ is a connected context-sensitive grammar. Now define a symbol valuation f′: N′ ∪ T → ℕ for G′ by:

f′(A) =^{def} s(2)^{2} · f(A)  for every A ∈ N
f′(Â) =^{def} s(2)^{2} · f(A) + s(2) for every A ∈ N
f′(a) =^{def} s(2)^{2} · f(a)  for every a ∈ T

Then every production in P′ is s-weakly growing with f′ as shown below. 29 Each rule from P grows at least by one with respect to f. The factor

Proof of Lemma 4-3

s(2)^{2} in the definition of f′ causes this growth rate to rise to s(2)^{2}. As 0 < s(2) ≤ s(1) · s(2) < s(2)^{2} (because s(1) ≥ 1 and s is strictly monotone increasing), the claim can be concluded for every rule of P′. To illustrate, we take a closer look at the second rule in P_{1}. Because AB → CD is s-weakly growing with f, the following applies:

s(1) · f(A) + s(2) · f(B) + 1 ≤ s(1) · f(C) + s(2) · f(D)

so

s(1) · s(2)^{2} · f(A) + s(2)^{3} · f(B) + s(2)^{2} ≤ s(1) · s(2)^{2} · f(C) + s(2)^{3} · f(D)

Thus, for the new rule AB̂ → ĈD, it holds that

s(1) · f′(A) + s(2) · f′(B̂) = s(1) · s(2)^{2} · f(A) + s(2) · s(2)^{2} · f(B) + s(2) · s(2)
≤ s(1) · s(2)^{2} · f(C) + s(2) · s(2)^{2} · f(D)

< s(1) · s(2)^{2} · f(C) + s(1) · s(2) + s(2) · s(2)^{2} · f(D)

= s(1) · f′(Ĉ) + s(2) · f′(D)

Thus we have G′ ∈ WGCSG_{s}. The second claim is true following [Boo69].

Proof of Lemma 4 □

It is possible to use the same idea for other position valuations. We even

5.1.1-4

have connectivity if there is no known transformation into Cremers normal form.

5.1.2 Efficient Simulation

When we simulate a derivation with a weakly growing context-sensitive gram-

5.1.2-1

mar related to a steady position valuation by a linear bounded automaton, we use the algorithm of Section 4 and Lemma 4. To estimate the time bound for the linear bounded automaton, we estimate the length of the derivation in the weakly growing context-sensitive grammar related to the steady monotone increasing position valuation by the value of the derived word. This is done by the natural infinite extension of the position valuation. Such an extension allows us to valuate arbitrarily long sentential forms. With every application of a rule, the value of the sentential form increases (at least by one).

30 Lemma 5 Let s be an infinite steady monotone increasing position valuation. Let G = ⟨N, T, S, P ⟩ be an s-weakly growing context-sensitive grammar, let u = u_{1} … u_{r}, v = v_{1} … v_{s} ∈ (N ∪ T)^{∗} be sentential forms with u ⟹ v, and let f: N ∪ T → ℕ^{+} be a symbol valuation for G. Then the following applies:

∑_{i=1}^{r} s(i) · f(u_{i}) + 1 ≤ ∑_{i=1}^{s} s(i) · f(v_{i})

That is, concerning steady position valuations, the positive growth rate of a rule induces a positive growth rate of the corresponding derivation step.

Proof of Lemma 5 Let (α → β) ∈ P be the rule used in the derivation step u ⟹ v. The growth rate of that rule is at least 1; we denote it by g. Let us now valuate the whole sentential forms u = u_{1}αu_{2} and v = u_{1}βu_{2}, and look at the growth rate of the derivation step u ⟹_{G} v. We obtain the value

g · w(s)^{|u_{1}|} where w(s)^{|u_{1}|} ≥ 1, if r is length-preserving, and g · w(s)^{|u_{1}|} + b where, additionally, b > 0, if it is length-increasing. As there are no lengthdecreasing rules, this implies the claim.

Proof of Lemma 5 □

As we saw in Section 4 in the construction of swallowers, in the case of

5.1.2-2

an unsteady position valuation it is not possible to build a natural extension such that the value of a sentential form increases with every application of a weakly growing rule (see Lemma 3). On the other hand, because of this effect there cannot exist a swallower for a steady position valuation. Thus we can estimate the length of a derivation generating a word w in a grammar G by the valuation of the word w itself.

We conclude from Lemma 5 and Definition 3:

5.1.2-3

Lemma 6 Let s be an infinite steady strictly monotone increasing position valuation. Let G = ⟨N, T, S, P ⟩ ∈ W GCSG_{s}, let f be an appropriate symbol valuation for G. Let c = max { f(A) : A ∈ N ∪ T }. Let v ∈ L(G). Then the length of a derivation S ⟹^{∗} v is not greater than

∑_{i=1}^{|v|} s(i) · c = c · ∑_{i=1}^{|v|} s(1) · w(s)^{i−1} ≤ w(s)^{|v|} · \frac{c · s(1)}{w(s) − 1}

31 Now we can estimate the computation time a linear bounded automaton

5.1.2-4

needs to simulate a weakly growing context-sensitive grammar related to a steady position valuation using Theorem 4, Lemma 4, and Lemma 6. (Here, T -NSPACE-TIME(s, t) denotes the class of languages that are accepted by a one-tape nondeterministic Turing machine with the given space bound s and the given time bound t; see [WW86].)

Theorem 6 Let s be a steady nonconstant position valuation. Let w = max\{w(s), \frac{1}{w(s)}\}. Then:

WGCSL_{s} ⊆ T -NSPACE-TIME(n, O(w^{n}))

5.2 Counters

We will introduce a counter as an instrument to lay down encoded weight

5.2-1

pieces, consisting of a string and some rules. We will use it in a simulation of a linear bounded automaton by a weakly growing context-sensitive grammar. The capacity of the counter used will cause a bound on the number of steps that can be simulated.

Definition 8 Let s be a steady strictly monotone increasing position valua-

Definition 8-1

tion, and let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Define a counter for G related to the position valuation s, also called an s-counter for G, to be a quintuple Z_{s,G} = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈ℕ^{+}}, P_{count}), such that:

• The components of the quintuple are

– N_{1} and N_{2} are nonempty subsets of N,

– N_{count} is a set of nonterminals (not necessarily a subset of N),

– (z_{n})_{n∈ℕ^{+}} is a sequence of start strings with z_{n} ∈ N_{count}^{n} for every n ∈ ℕ^{+}, and

– P_{count} is a finite subset of (N_{2}·N_{count}^{∗}×N_{1}·N_{count}^{∗})∪(N_{count}^{∗}×N_{count}^{∗}); every rule in P_{count} is length-preserving.

• There exists a symbol valuation f: N ∪ N_{count} ∪ T → ℕ where

– f is a symbol valuation for G, i.e., every rule in P is s-weakly growing with f,

– every rule in P_{count} is s-weakly growing with f, and 32

– for every X ∈ N_{1}, Y ∈ N_{2}, it holds that f(X) < f(Y).
We say that f|_{N_{1}∪N_{2}∪N_{count}} is a symbol valuation for Z.

Definition 8-2 If N_{count} ⊆ N and P_{count} ⊆ P, we also call Z_{s,G} an s-counter in G. If s and G are clear from the context, the subscripts are dropped.

For every X ∈ N_{1} and Y ∈ N_{2}, the counter counts the weight piece

5.2-2

f(Y) − f(X) by applying an appropriate rule out of N_{2} · N_{count}^{∗} × N_{1} · N_{count}^{∗} (and after that possibly some rules out of N_{count}^{∗} × N_{count}^{∗}) on the string Y z_{n}, where z_{n} is one of the start strings of Z. This results in a string Xz′_{n} of the same length. Another weight can be counted applying rules as mentioned above on Y z′_{n}, and so on. To use the counter to count several amounts of weight, we apply corresponding increment rules (which are not in P_{count}, but will be added to P in order to use the counter in G).

Definition 9 Let s be a steady strictly monotone increasing position valua-

Definition 9-1

tion, let G⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Let Z be an s-counter for G, and let f be a symbol valuation for G and for Z.

The set ρ(Z, f) of increment rules for Z with f is defined by:

Definition 9-2

ρ(Z, f) =^{def} { (X → Y) : X ∈ N_{1}, Y ∈ N_{1} ∪ N_{2}, and f(X) < f(Y) }

Consider a derivation starting with a string of the form Xz_{n}, where X ∈

5.2-3

N_{1} and z_{n} is the start string with index (and length) n. We are interested in the number of times an increment rule can be used (and the weight piece generated by it can be handled) in such a derivation. So, we define the capacity K_{Z}(n) to be the maximum number of times that it is possible to have an occurrence of an increment rule in a derivation starting with Xz_{n} and ending with X′z̃, where X′ ∈ N_{1} and |z̃| = |z_{n}|. Note that there are two kinds of increment rules. The first kind (which we call a “collecting weights” rule) leaves the first symbol in N_{1}. The second kind of increment rule (which replaces the first symbol from one in N_{1} to one in N_{2}) is the kind of increment rule that directly influences the counter.

Definition 10 Let s be a steady strictly monotone increasing position valuation, let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}, let Z be an s-counter for G, let z_{n} be the start string with index n, and let V_{Z,G} be the set of all symbol valuations

33 for Z and G. The capacity function K_{Z}: ℕ^{+} →ℕ^{+} of Z is defined as follows:

K_{Z}(n) =^{def} max \{ |\{ j : r_{j} ∈ ρ(Z, f) \}| : \begin{matrix}f ∈ V_{Z,G}, X, X′ ∈ N_{1}, z̃ ∈ N_{count}^{n}, k ∈ ℕ, \\ (r_{1}, …, r_{k}) ∈ (P_{count} ∪ ρ(Z, f))^{k}, \\ Xz_{n} ⟹_{r_{1}} … ⟹_{r_{k}} X′z̃ \end{matrix} \}

Because the set N is finite and each of the rules is length-preserving, the capacity of a counter certainly is well defined. Because of the possibility of collecting weights (in fact, we only need to extend N_{1} to raise the capacity of a counter by a constant factor), there is for every counter Z and every c ∈ ℕ^{+} a counter Z′ with K_{Z′} = c · K_{Z}.

Let us now have a look at a specific counter to see how it works.

5.2-4

Example 4 Let s be a steady strictly monotone increasing position val-

Example 4-1

uation. Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} with {#, M} ⊆ N. Define Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈ℕ^{+}}, P_{count}) by: N_{1} =^{def} {M}, N_{2} =^{def} {#}, N_{count} =^{def} {[0], [1], …, [k]} for a k ∈ ℕ^{+}, z_{n} =^{def} [0]^{n} for each n ∈ ℕ^{+}, and P_{count} consisting of the rules:

\begin{aligned}(R1) & #[i] & → M[i + 1] \\ (R2) & [i + 1][i] & → [i][i + 1] \end{aligned} for i = 0, …, k − 1

The symbol valuation f defined by

f(M) =^{def} 1, f(#) =^{def} 2, f([i]) =^{def} i + 1 for i = 0, …, k

shows that Z is an s-counter for G. M → # is the only possible increment rule, thus the capacity is K_{Z}(n) = k · n.

If we change rule (R2) to

Example 4-2

(R2′) [i + 1][i] → [0][i + 1] for i = 0, …, k − 1

we obtain a counter with polynomial capacity. (In the symbol valuation define f([i]) =^{def} w(s)^{i} for i = 0, …, k.)

Example 4 □

We have seen counters with linear and with polynomial capacities. What

5.2-5

about exponential capacity? As we reach for an inversion of Theorem 6, this is our goal.

Let us check the possible capacity for a counter that follows the algorithm

5.2-6

“treat the string as a number to a certain base, and add up arithmetically.” We look at an example first.

34 Example 5 Let s_{2} be the position valuation defined by s_{2}(i) =^{def} 2^{i−1} for

Example 5-1

every i ∈ ℕ^{+}. Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s_{2}} with {#, M} ⊆ N. Define Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈ℕ^{+}}, P_{count}) by N_{1} =^{def} {M}, N_{2} =^{def} {#}, N_{count} =^{def} {[0], [1], [U]}, z_{n} =^{def} [0]^{n} for each n ∈ ℕ^{+} and P_{count} consisting of the rules:

(R1) #[0] → M[1]  (R3) [U][0] → [0][1]
(R2) #[1] → M[U] (R4) [U][1] → [0][U]

Using rules (R1)–(R4) above, together with the rule M → #, for every start string z_{n} the following derivation steps are possible in Z:

\begin{matrix}Mz_{n} = & M[0][0][0] … [0] ⟹^{∗} M[1][0][0] … [0] ⟹^{∗} M[U][0][0] … [0] \\ ⟹^{∗} & M[0][1][0] … [0] ⟹^{∗} M[1][1][0] … [0] ⟹^{∗} M[U][1][0] … [0] \\ ⟹^{∗} & M[0][U][0] … [0] ⟹^{∗} M[0][0][1][0] … [0] \\ ⟹^{∗} & … ⟹^{∗} M[U][U] … [U] \end{matrix}

At first glance, this looks like an s_{2}-counter with capacity

2 · ∑_{i=1}^{n} 2^{i−1} = ∑_{i=1}^{n} 2^{i} = 2^{n+1} − 2 ≥ 2^{n}

Now let f: N_{1} ∪ N_{2} ∪ N_{count} → ℕ be a symbol valuation. Then we have:

For (R3):

1 · f([U]) + 2 · f([0]) < 1 · f([0]) + 2 · f([1])
which implies f([U]) − f([1]) < f([1]) − f([0])

For (R4):

1 · f([U]) + 2 · f([1]) < 1 · f([0]) + 2 · f([U])
which implies f([1]) − f([0]) < f([U]) − f([1])

Both of these inequalities cannot be fulfilled at the same time. Thus

Example 5-2

there exists no symbol valuation with which all rules of P_{count} are s_{2}-weakly growing. This implies that Z is not an s_{2}-counter, for every G ∈ WGCSG_{s_{2}}.

Example 5 □

35 The reason is, that in every rule we transport a portion of the weight piece

5.2-7

plus an increment for making the rule weakly growing to the right. When all these portions and increments come together, they add up to a value that must not exceed the original weight piece, because this sum is to be handled in the same way, arbitrarily often.

5.2-8 We will now look at the upper bound for the capacity of a counter Z_{s,G} which works after the following mechanism: It treats the start string as a number (where each digit of that number is represented by several symbols (bits) of the string) and increments this encoded number arithmetically. We fix the number of symbols used to represent a digit by l ∈ ℕ. How many different digits [0], [1], …, [i_{max}] can now be represented by l bits of the string without violating the property of Z_{s,G} to be an s-counter? We have seen in Example 5 that, e.g., for l = 1 to choose i_{max} = 1 (that is, choosing the base of the number representation to be 2) violates this property.

This number of digits representable by l bits while respecting the s-

5.2-9

counter property determines the base of the number representation that we use to count weight pieces. Thus, it also determines the maximal capacity reachable by such a counter.

In the following lemma, [0], [1], …, [i_{max}], and [U] are metasymbols, each

5.2-10

standing for l letters (bits) that encode the digits 0, 1, …, i_{max} of the number representation, and the l letters of [U] represent the overflow, which contains 0 and a carry for the next position.

Lemma 7 Let s be an infinite steady strictly monotone increasing position

Lemma 7-1

valuation. Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} with {#, M} ⊆ N, and let Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈ℕ^{+}}, P_{count}) be a counter with M ∈ N_{1}, # ∈ N_{2}. Let l ∈ ℕ^{+}.

Lemma 7-2 If Z_{s,G} works after the following scheme (where [0], [1], …, [i_{max}], [U] ∈ N_{count}^{l}, i_{max} ∈ ℕ, i = 0, …, i_{max} − 1):

(R1)  #[i] → M[i + 1] (R3)  [U][i] → [0][i + 1]
(R2) #[i_{max}] → M[U]  (R4) [U][i_{max}] → [0][U]

and if Z_{s,G} is an s-counter, then the capacity of the counter Z_{s,G} is bounded by

K_{Z}(n) ≤ (c + 2) · ⌈w(s)^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋}

where c is a constant depending on Z_{s,G}.

36 Note that for w(s)^{l} ≤ 2 the capacity is at most linear, but for w(s)^{l} > 2

5.2-11

it is at most exponential. As we stated above, the goal of this lemma is to estimate i_{max}.

Proof of Lemma 7 Let f be a symbol valuation for Z. Define a function

Proof of Lemma 7-1

g: N_{count}^{l}→ℕ^{+} by g(a_{1} … a_{l}) =^{def} ∑_{i=1}^{l} s(i)·f(a_{i}), where a_{1}, …, a_{l} ∈ N_{count}. That

is, g valuates the metasymbols [0], [1], …, [i_{max}], [U], each represented by l letters out of N_{count}, by condensing the symbol and the position valuation. Let w denote the growth factor w(s). Then we have:

For (R3):

Proof of Lemma 7-2

g([U]) − g([0]) < w^{l} · (g([i + 1]) − g([i])) for i = 0, …, i_{max} − 1

For (R4):

Proof of Lemma 7-3

g([U]) − g([0]) < w^{l} · (g([U]) − g([i_{max}]))

Let μ = g([U]) − g([0]). This implies

μ =^{def} g([U]) + (−g([i_{max}]) + g([i_{max}])) + ⋯ + (−g([1]) + g([1])) − g([0])
= (g([U]) − g([i_{max}])) + (g([i_{max}]) − g([i_{max} − 1])) + ⋯ + (g([1]) − g([0]))

> \frac{1}{w^{l}} · μ + \frac{1}{w^{l}} · μ + ⋯ + \frac{1}{w^{l}} · μ

i_{max}+1 times
= \frac{i_{max} + 1}{w^{l}} · μ

For (R1) and (R2), μ > 0, so i_{max} + 1 < w^{l}, from which it follows that i_{max} = ⌈w^{l} − 2⌉ (which means i_{max} = 0 for w^{l} ≤ 2). Thus, we have a number

representation to the base ⌈w^{l} − 1⌉.

Starting with M[0]^{⌊^{\frac{n}{l}}⌋}α, where α ∈ N_{count}^{∗} with |α|+l·⌊\frac{n}{l}⌋ = n, the string

Proof of Lemma 7-4

M[i_{max}]^{⌊^{\frac{n}{l}}⌋}α is derivable following the scheme (R1) through (R4) plus the increment rule (M → #). In such a derivation the increment rule is applied

\begin{matrix}⌊ & \frac{n}{l} & ⌋ \\ ∑ \\ i=1 \end{matrix} i_{max} · (i_{max} + 1)^{i−1}

37 times. Then, with (R4), or (R2) if necessary, we can change the rightmost digit (i.e., metasymbol) to [U]: in doing so, the other digits change to [0]. Again we can add up (i.e., apply (M → #) and the rules from the scheme) and thus derive M[i_{max}]^{⌊^{\frac{n}{l}}⌋−1}[U]α. Using this mechanism several times, we can fill up the string with overflows [U]. Thus, we derive M[U]^{⌊^{\frac{n}{l}}⌋}α.

Unless P_{count} contains some rules to fill up α, now no more rules apply.

Proof of Lemma 7-5

The increment rule (M → #) was applied

\begin{matrix}⌊ & \frac{n}{l} & ⌋ \\ ∑ \\ i=1 \end{matrix}(i_{max} + 1) · (i_{max} + 1)^{i−1} = (i_{max} + 1) · ∑_{i=0}^{⌊\frac{n}{l}⌋−1}(i_{max} + 1)^{i}

times. If P_{count} contains some rules to fill up α, that is, to do derivation steps [U]α_{j} ⟹ [0]α_{j+1}, where α_{0} = α, α_{j} ∈ N_{count}^{∗} for j ∈ ℕ, the number of these steps is bounded by a constant c, independent of n.

To derive M[U]^{⌊^{\frac{n}{l}}⌋}α_{c}, the increment rule is used

Proof of Lemma 7-6

(i_{max} + 1) · ∑_{i=0}^{⌊\frac{n}{l}⌋−1}(i_{max} + 1)^{i} + c · (i_{max} + 1)^{⌊^{\frac{n}{l}}⌋}

times. Thus, the capacity of the counter Z_{s,G} can be estimated by:

K_{Z}(n) ≤ c · ⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋} + ⌈w^{l} − 1⌉ · ∑_{i=0}^{⌊\frac{n}{l}⌋−1} ⌈w^{l} − 1⌉^{i}

= c · ⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋} + ⌈w^{l} − 1⌉ · \frac{⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋} − 1}{⌈w^{l} − 1⌉ − 1}

= c · ⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋} + ⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋} − 1 + \frac{⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋} − 1}{⌈w^{l} − 1⌉ − 1}

≤ (c + 2) · ⌈w^{l} − 1⌉^{⌊^{\frac{n}{l}}⌋}

Proof of Lemma 7 □

The upper bound stated in the lemma is optimal. That is, we can really

5.2-12

find a counter working according to this adding mechanism and reaching the stated capacity. We put Lemma 8 with the exponent rounded up instead of rounded down, only because of technical reasons in the use of the lemma.

38 Lemma 8 Let s be an infinite steady strictly monotone increasing position valuation and G ∈ W GCSG_{s} with at least two different nonterminals, and let c ∈ ℕ^{+}. Let l ∈ ℕ. Then there exists an s-counter Z, that has a capacity with

K_{Z}(n) ≥ c · ⌈w(s)^{l} − 1⌉^{⌈^{\frac{n}{l}}⌉} for n ∈ ℕ^{+}, n ≥ l

Proof of Lemma 8 First we consider c = 1. We define an s-counter

Proof of Lemma 8-1

Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈ℕ^{+}}, P_{count})

following the scheme in Lemma 7. We will use the symbols of the string that are not used in a digit, which only occurs if n is not divisible by l, to “cheat” by using them to encode an additional digit. Thus we define:

N_{1} =^{def} {M} N_{2} =^{def} {#}
N_{count} =^{def} {D, [0], [1], …, [i_{max}], [U]} ∪ {⟨0⟩, ⟨1⟩, …, ⟨i_{max}⟩, ⟨U⟩} where i_{max} = ⌈w(s)^{l} − 2⌉

Each digit “i” is represented by D^{l−1}[i], and the start strings are z_{n} =

(D^{l−1}[0])^{⌊^{\frac{n}{l}}⌋} ⟨0⟩^{nmodl} for every n ∈ ℕ. The set P_{count} consists of the following rules (where i = 0, …, i_{max} − 1):

(R1)  #D^{l−1}[i] → MD^{l−1}[i + 1] (R3)  [U]D^{l−1}[i] → [0]D^{l−1}[i + 1]
(R2) #D^{l−1}[i_{max}] → MD^{l−1}[U]  (R4) [U]D^{l−1}[i_{max}] → [0]D^{l−1}[U]

\begin{aligned}(R5) & [U]⟨i⟩ & → [0]⟨i + 1⟩ \\ (R6) & [U]⟨i_{max}⟩ & → [0]⟨U⟩ \end{aligned}

Now we define a symbol valuation f: N_{1} ∪ N_{2} ∪ N_{count} → ℕ^{+} by (where i = 1, …, i_{max}):

f(M) =^{def} 1  f(D) =^{def} 1  f(#) =^{def} ⌈w(s)^{l}⌉
f([0]) =^{def} 1  f([i]) =^{def} i + 1  f([U]) =^{def} ⌈w(s)^{l}⌉
f(⟨0⟩) =^{def} 1 f(⟨i⟩) =^{def} i · ⌈w(s)^{l}⌉ f(⟨U⟩) =^{def} (⌈w(s)^{l}⌉ − 1) · ⌈w(s)^{l}⌉

It can be checked easily that the given rules all are s-weakly growing with f. 39 The rules (R5) and (R6) give us the possibility to “cheat” by using an

Proof of Lemma 8-2

additional digit, if l does not divide n. The capacity now is calculated just as

in the proof of Lemma 7, thus applies K_{Z}(n) ≥ ⌈w(s)^{l} − 1⌉^{⌈^{\frac{n}{l}}⌉}. By collecting weights we get a counter Z′ with K_{Z′} = c · K_{Z} for every c ∈ ℕ^{+}.

Proof of Lemma 8 □

5.3 Simulation of Time-Bounded Linear Automata

The counters introduced in Lemma 8 now will be used in a simulation of a

5.3-1

time-bounded linear-bounded automaton instead of the swallower we used in Section 4. The time bounds for linear bounded automata that can be managed with this counter are determined by the counter’s capacity.

Theorem 7 Let w ∈ ℕ^{+}, let q ∈ ℚ with 0 < q < 1. Then:

T -NSPACE-TIME(n, O(w^{q·n})) ⊆ WGCSL_{w}

Proof of Theorem 7 We only describe the intuitive operation of the gram-

Proof of Theorem 7-1

mar simulating a given linear-bounded automaton on a given w ∈ ℕ^{+}. The construction of the grammar itself then is straightforward.

Let M be any linear bounded automaton that recognizes its language

Proof of Theorem 7-2

L(M) in the time c · w^{q·n} with an appropriate c ∈ ℕ^{+}, and let s be an infinite steady position valuation with w(s) = w.

Similar to Section 4, case (iii), we divide the sentential form into left-hand

Proof of Theorem 7-3

and right-hand parts: In the left-hand part the step-by-step simulation of the automaton takes place in the same manner as in the simulation mentioned above, except that we use tape compression; in the right-hand part, a counter is situated (see Figure 4).

Proof of Theorem 7-4 We choose an appropriate compression factor k so that q < \frac{k−1}{k}, and for this k we choose the width l of a digit so that ⌈w^{l}⌉ ≥ w^{l·q· \frac{k}{k−1}} + 1. Note that

this expression is equivalent to ⌈w^{l} − 1⌉^{\frac{k−1}{k} · \frac{1}{l}} ≥ w^{q}.

Following Lemma 8 we can find an s-counter Z with the capacity K_{Z}(m) ≥

Proof of Theorem 7-5

c · ⌈(w)^{l} − 1⌉^{⌈^{\frac{m}{l}}⌉} where m =^{def} ⌈\frac{k−1}{k} · n⌉ is the length of the part of the sentential form where the counter operates in the simulation for an input of length n. This implies

K_{Z}(m) ≥ c · ⌈w^{l} − 1⌉^{⌈\frac{k−1}{k} · \frac{n}{l}⌉} ≥ c · w^{q·n}

40

\overbrace{[\begin{matrix}LBA simulation \\ compressed \end{matrix}]}^{\frac{1}{k} ·n}\overbrace{\underbrace{D^{l−1}[i_{1}]}_{lowest digit} \underbrace{D^{l−1}[i_{2}]}_{2. digit}… \underbrace{D^{l−1}[i_{max}]}_{highest digit}}^{\frac{k−1}{k} ·n}

length of the derived word (i.e., the original input)

Figure 4: Simulation with a steady position valuation: sentential form

This means that if M accepts an input word, the simulation can be completed. Then the k-tuples of the compressed LBA-simulation are transformed into terminals and expanded at the same time. Together with the expansion, the counter disappears.

This can be expressed by a WGCSG with position valuation s in the

Proof of Theorem 7-6

following way. First we state the length of the sentential form is exactly n, i.e., the length of the terminal word to be produced. The reason is that the length of the part of the sentential form where the counter operates is m = ⌈\frac{k−1}{k} · n⌉, as stated above, and the length of the part where the

simulation takes place can be organized such that it equals ⌊\frac{1}{k} · n⌋, e.g., by compressing k symbols of the input for the LBA (the later terminal word) in every simulation symbol, except for the rightmost one: Here we encode k′ := k + n mod k symbols.

Now the decompression works in the following way: First, the rightmost

Proof of Theorem 7-7

simulation symbol is transformed and decompressed into k′ terminal symbols, where k′ − 1 of the (leftmost) counter symbols disappear. Then the terminal symbols are passed through to the right. By valuating the terminal symbols greater than the maximum value of all other symbols, these rules are weakly growing related to s. The same procedure is done with the now-rightmost symbol, and then step by step with all the simulation symbols, where in this and the following steps k′ := k.

For a detailed and explicit construction of the grammar, see [Nie94].

Proof of Theorem 7-8

Proof of Theorem 7 □

5.3-2 Note that the requirement q < \frac{k−1}{k} is for a trick only: In order to ex-

ceed the time bound with the capacity of the counter, we strengthen it by 41 the choice of l, the number of letters representing a digit (see Lemma 8, and regard additionally the limited space for the counter in the simulating

sentential form). But such an l, fulfilling ⌈w^{l} − 1⌉^{\frac{k−1}{k} ·n· \frac{1}{l}} ≥ w^{q·n}, does not exist for \frac{k−1}{k} ≤ q, so there is a gap between Theorem 6 and Theorem 7. As the construction technique used to build a counter with exponential capacity does not lead further (see Lemma 7), closing this gap is a nontrivial problem.

6 Characterizing the Exponential Time Hierarchy of CSL

In the previous sections we looked at several position valuations, struc-

6-1

turing and investigating them. Now we will gain an overview of the different classes of weakly growing context-sensitive languages related to different position valuations.

For a constant position valuation, we obtain the same grammars as if we

6-2

had no position valuation at all, namely the quasi-growing context-sensitive grammars, which characterize GCSL ([BL92], compare Section 2). For every unsteady position valuation, we obtain the language class CSL, as we saw in Section 4. Allowing zero points for position valuations, we also obtain a characterization of CSL, as we mentioned before (see Section 2).

Note that in Definition 3 we gave an equivalent characterization for the

6-3

property “unsteady,” which does not hold for position valuations with zero points: A position valuation s without zero points is unsteady if and only if s has at least three valuated positions and s has a blip, i.e., a position j with s(j)^{2} ≠ s(j − 1) · s(j + 1). In Section 4, in fact, we used this equivalent characterization (e.g., in the values of the symbols of a swallower). Essentially, there is still something to show in cases where s has only two valuated positions or where s has no blip according to the definition given above, which is the case if s has only one nonzero point, and this is the first or the last valuated position, or if s has nonzero points at the first and the last position, separated at least by two zero points. On the other hand, the proof technique we use for these cases works for each position valuation with zero points. Therefore we formulate the next theorem and give a proof here. Theorem 8 Let s be a position valuation with zero points. Then:

WGCSL_{s} = CSL

42 Proof of Theorem 8 It is sufficient to show CSL ⊆ WGCSL_{s}. And it is

Proof of Theorem 8-1

sufficient to show this claim for finite position valuations s. So let s be a finite position valuation with zero points.

As the definition of WGCSL_{s} implies that s is not constantly 0, Theorem 2

Proof of Theorem 8-2

applies, and thus WGCSL_{s} is closed under transposition. Theorem 4 can be adapted in the following sense: Let m be the greatest position valuated by s. Define \overline{s}: ℕ^{+} → ℕ by: \overline{s}(i) =^{def} s(m − i + 1) for i = 1, 2, …, m. Then WGCSL_{s} = WGCSL\overline{s}.

This especially means we can assume that there exists a zero point j with

Proof of Theorem 8-3

s(j + 1) = c ≠ 0. Regarding these two positions, the “growth factor” in fact is not defined, but it can be seen as arbitrarily large. Thus, we can construct a counter similar to the one in Section 5.2 that counts in an arbitrarily given number representation. (For j ≠ 1 we add a left-hand context of length j − 1 to the rules in the proof of Lemma 8, we can choose l = 1, and the symbol valuation is constructed in the same way as it was there.) Now given a linear bounded automaton with the exponential time bound b^{n} = (b^{2})^{\frac{1}{2} ·n}, b ≥ 2, we construct a grammar similar to the one in the proof of Theorem 7, where we choose q = \frac{1}{2}, k = 2, and b^{2} instead of ⌈w(s) − 1⌉ as the base of the number representation the counter uses. Thus, the linear bounded automaton can be simulated by an s-weakly growing context-sensitive grammar.

Proof of Theorem 8 □

Note that here we do not have a gap between the base of the time bound-

6-4

ing function of the linear bounded automaton and the base of the number representation the counter uses (in contrary to Theorem 7). Therefore, here we do not need the trick of representing a digit by several symbols, and the requirement q < \frac{k−1}{k} can be dropped, as the base of the number representation the counter uses can be chosen freely to ensure its capacity exceeds the time bound.

For every steady position valuation s, we saw in Section 3.2 that the

6-5

corresponding class of weakly growing context-sensitive languages is characterized by the growth factor w(s), and in Theorems 6 and 7 the following was shown. Proposition 3 Let s be a steady nonconstant position valuation. Let w = max \{w(s), \frac{1}{w(s)}\}. For every q ∈ ℚ^{+}, 0 < q < 1, it holds that

T -NSPACE-TIME(n, O(w^{q·n})) ⊆ WGCSL_{s} = WGCSL_{w} ⊆ T -NSPACE-TIME(n, O(w^{n}))

43

[figure: T -NSPACE-TIME(n, O(v^{n})); for \frac{log(w)}{log(v)} < q < 1; T -NSPACE-TIME(n, O(v^{q·n})); T -NSPACE-TIME(n, O(w^{n})); WGCSL_{v}; WGCSL_{w}]

Figure 5: Relations for growth factors v > w > 1

Corollary 1 For v, w ∈ ℕ^{+} with w < v it holds that WGCSL_{w} ⊆ WGCSL_{v}.

The resulting relations for different growth factors are depicted in Fig-

6-6

ure 5.

As every polynomial time bound can be exceeded by every exponential

6-7

time bound, the following can be concluded. To denote classes of sets accepted in polynomial time bounds, we use the notation pol for the set of all polynomials in a single variable n.

Corollary 2 For every steady nonconstant position valuation s, it holds that

T -NSPACE-TIME(n, pol) ⊆ WGCSL_{s}

We therefore have all the relations depicted in Figure 6, where we con-

6-8

centrated on some specific classes because of clarity. Thus the weakly growing context-sensitive languages related to steady position valuations build a linearly inclusion-ordered hierarchy that characterizes the exponential time hierarchy for context-sensitive languages in the sense that the one collapses to a certain level if and only if the other collapses to a corresponding level. Additionally, with the counters we introduced in Section 5.2 and the idea of construction in the proof of Theorem 7, the following can be shown.

44

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; CSL = WGCSL_{s}, s unsteady or zero points; T -NSPACE-TIME(n, O(2^{k·n})); WGCSL_{2^{k}} = WGCSL_{\frac{1}{2^{k}}}; T -NSPACE-TIME(n, O(2^{q·k·n})); for \frac{k−1}{k} < q < 1; T -NSPACE-TIME(n, O(2^{(k−1)·n})); WGCSL_{2^{k−1}} = WGCSL_{\frac{1}{2^{k−1}}}; WGCSL_{2^{2}} = WGCSL_{\frac{1}{4}}; WGCSL_{2} = WGCSL_{\frac{1}{2}}; WGCSL_{\frac{3}{2}}; WGCSL_{\frac{4}{3}}; T -NSPACE-TIME(n, O(2^{2·n})); T -NSPACE-TIME(n, O(2^{q·2·n})); for \frac{1}{2} < q < 1; T -NSPACE-TIME(n, O(2^{n})); T -NSPACE-TIME(n, O(2^{q·n})); for 0 < q < 1; WGCSL_{\frac{j+1}{j}}; T -NSPACE-TIME(n, pol); GCSL = WGCSL_{C}, C constant]

Figure 6: Exponential-time CSL and WGCSL hierarchies 45 Theorem 9 Let s be a steady nonconstant position valuation. The closure of WGCSL_{s} under inverse homomorphism is CSL. As well, the closure of WGCSL_{s} under k-bounded homomorphism is CSL.

Proof of Theorem 9 Let L ∈ CSL, and let M be a linear bounded au-

Proof of Theorem 9-1

tomaton that accepts L in the time t · 2^{c·n}. Let Σ be the input alphabet. Analogously to the grammar in the proof of Theorem 7, we construct an

Proof of Theorem 9-2

s-weakly growing context-sensitive grammar G that simulates M (without tape compression) and uses a counter just like the one we used in the proof mentioned above.

For an input word of length n, we choose a start string of length m for

Proof of Theorem 9-3

the counter, where m ≥ \frac{l·c}{log(w(s)−1)} · n and l ∈ ℕ. Thus we reach at least the capacity

K_{Z}(m) ≥ t · (w(s)^{l} − 1)^{⌈^{\frac{m}{l}}⌉} ≥ t · (w(s)^{l} − 1)^{⌈\frac{l·c}{l·log(w(s)^{l}−1)} ·n⌉}
≥ t · 2^{log(w(s)^{l}−1)·⌈\frac{c}{log(w(s)^{l}−1)} ·n⌉} ≥ t · 2^{c·n}

which means, if M accepts an input word, its work is simulated completely.

Now we can expand each symbol a ∈ Σ to a♢^{⌈\frac{l·c}{log(w(s)^{l}−1)}⌉}, where ♢ ∉ Σ

Proof of Theorem 9-4

is a new symbol. Together with the expansion, the counter disappears.

We define a homomorphism h: Σ^{∗} →(Σ ∪ \{♢\})^{∗} by h(a) =^{def} a♢^{⌈\frac{l·c}{log(w(s)^{l}−1)}⌉}

Proof of Theorem 9-5

for every a ∈ Σ. Then h(L) = L(G).

To prove the claim for k-bounded homomorphism, define h: (Σ ∪ {♢})^{∗}→

Proof of Theorem 9-6

Σ^{∗} by h(a) =^{def} a for every a ∈ Σ, h(♢) =^{def} ε. Then h is k-bounded for L(G) with k =^{def} ⌈\frac{l·c}{log(w(s)^{l}−1)}⌉, and h(L(G)) = L.

Proof of Theorem 9 □

We point out that s is nonconstant, not only because the counter is not

6-9

defined otherwise, but also because GCSL is closed under inverse homomorphism [BL92] (and thus also under k-bounded homomorphism, [GGH69]).

We obtain the following connections between the closure of WGCSL_{s} un-

6-10

der inverse homomorphism for steady position valuations s, the transformability of a grammar from WGCSG_{s} into Cremers normal form for unsteady position valuations s, and the exponential time hierarchy of CSL.

46 Theorem 10 Let w > 1, and let s be a steady position valuation with w(s) = w. The following statements are equivalent:

a) WGCSL_{w} = CSL.

b) WGCSL_{w} is closed under inverse homomorphism.

c) For every unsteady position valuation s̃, for every grammar G ∈ WGCSGs̃, there exists a grammar G′ ∈ WGCSG_{s} in Cremers normal form with L(G′) = L(G).

d) There exists an unsteady position valuation s̃ satisfying the condition of c) above.

Additionally, a) implies:

e) T -NSPACE-TIME(n, O(w^{n})) = T -NSPACE(n),

and from this it can be concluded:

f) WGCSL_{v} = CSL for every v > w.

7 Conclusion

We have seen a characterization of CSL by weakly growing context-sensitive

7-1

grammars related to an unsteady position valuation (Section 4) and a characterization of the exponential time hierarchy of CSL by classes of weakly growing context-sensitive languages related to steady position valuations (Section 6). Equally interesting, we consider the question of whether the exponential time hierarchy for linear bounded automata collapses.

Theorem 10 proves that the following problems are equivalent:

7-2

• For every weakly growing context-sensitive grammar related to an unsteady position valuation s̃, does there exist an equivalent grammar in a normal form of bounded order that is weakly growing context-sensitive related to a steady position valuation s?

• Is WGCSL_{s} closed under inverse homomorphism for a steady position valuation s?

47 • Does the hierarchy of weakly growing context-sensitive language classes

corresponding to different growth factors collapse down to a certain level? That is, do CSL and WGCSL_{s} coincide for a steady position valuation s?

• Does the exponential time hierarchy for CSL collapse up to CSL? That is, do CSL and T -NSPACE-TIME(n, O(w^{n})) coincide for a certain w ∈ ℕ^{+}?

If in the first question we allow an arbitrary position valuation instead of a steady one, we also must restrict ourselves to normal forms of order 2 (and thus end up with a steady position valuation again). The reason lies in the fact that for each context-sensitive grammar there exists an equivalent grammar of order 3 that is in WGCSG_{s}, where s is an arbitrary unsteady position valuation with three valuated positions. This can be shown in the following way:

We restrict ourselves to the case s(1) < s(2). The others work analogously. Given a context-sensitive grammar G, first G is transformed into an equivalent grammar G′ in Cremers normal form. Then we associate an additional encoded weight piece with every rule such that all the rules become weakly growing related to s with an appropriately defined symbol valuation f (this idea is similar to the one in the proof of Theorem 2). Then we add rules to pass those weights through to the right and a swallower (compare Section 4, case (iii)). Thus every step of the original derivation can be simulated by using the corresponding rule of the new grammar, passing the encoded weight through to the right, and swallowing it.

Because of Theorem 3 we know that asking for a normal form of bounded

7-3

order in the case of a steady position valuation is equivalent to asking for a normal form of order 2. Remember that our notation of a characterization of one hierarchy by another means that the one collapses if and only if the other does. More precisely, we have a chain of inclusions between language classes where the members of that chain alternate between the two hierarchies.

In this context, it would be interesting to close the gap between Theo-

7-4

rems 6 and 7, that is, to answer the question whether

WGCSL_{w} = T -NSPACE-TIME(n, O(w^{n})) ?

48

Buntrock and Niemann Weakly Growing CSGs (Ref)

8 Acknowledgments

We thank Hans-Jörg Burtschick for pointing out a former version of Exam-

8-1

ple 2, and Steffen Reith for the idea of how to simplify the proof of Lemma 6. Also we are grateful to Carmen Schwenkel for allowing us to include some results of her thesis paper [Sch93], extending them for arbitrary steady position valuations (Example 1, Theorem 1, and Theorem 3, also, the idea to build weakly growing grammars), and of her prethesis paper [Sch92], also extended (the separation of WGCSG_{s} and CSG in Section 2). Further, we are very grateful to an anonymous LATIN’95 referee and the anonymous CJTCS referees of our paper. All of them did an extraordinary job. So did the managing editor and the copy editor of the Chicago Journal of Theoretical Computer Science who worked on our paper, Michael J. O’Donnell and Lisa Clark. Last, but not least, we thank Eric Allender for his constructive help.

Acknowledgement of support: Gerhard Buntrock’s work was partly supported by a grant from the DFG (DFG-Projekt Wa 847/1-1).

References

[BL92] Gerhard Buntrock and Krzysztof Loryś. On growing contextsensitive languages. In Werner Kuich, editor, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, volume 623 of Lecture Notes in Computer Science, pages 77–88, Berlin, Heidelberg, New York, 1992. Springer-Verlag.

[BL94] Gerhard Buntrock and Krzysztof Loryś. The variable membership problem: succinctness versus complexity. In Patrice Enjalbert, Ernst W. Mayr, and Klaus W. Wagner, editors, Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science, volume 775 of Lecture Notes in Computer Science, pages 595–606, Berlin, Heidelberg, New York, 1994. Springer-Verlag.

49 [BO95] Gerhard Buntrock and Friedrich Otto. Growing context-

sensitive languages and Church-Rosser languages. In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 313–324. Springer-Verlag, 1995. To appear in Information and Computation.

[Boo69] Ronald V. Book. Grammars with time functions. Dissertation, Harvard University, Cambridge, Massachusetts, February 1969.

[Bör85] Egon Börger. Berechenbarkeit, Komplexität, Logik. Friedrich Vieweg & Sohn, Braunschweig, Wiesbaden, 1985. A third edition appeared 1995. English edition: [Bör89].

[Bör89] Egon Börger. Computability, Complexity, Logic, volume 128 of Studies in Logic and the Foundations of Mathematics. North Holland, Amsterdam, 1989. The German original appeared as: [Bör85].

[Bun93] Gerhard Buntrock. Growing context-sensitive languages and automata. Technical Report 69, Fakultät für Mathematik und Informatik, Universität Würzburg, September 1993.

[Bun96] Gerhard Buntrock. Wachsende kontextsensitive Sprachen. Habilitation thesis, Fakultät für Mathematik und Informatik, Universität Würzburg, July 1996. English title: Growing contextsensitive languages.

[Cho59] Noam Chomsky. On certain formal properties of grammars. Information and Control, 2:137–167, 1959.

[Coo79] Stephen A. Cook. Deterministic CFL’s are accepted simultaneously in polynomial time and LOG squared space. In M. Fischer, editor, Eleventh Annual ACM Symposium on Theory of Computing, pages 338–345. ACM, 1979. The results of this paper are contained in [vBCMV83].

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

50 [DW86] Elias Dahlhaus and Manfred K. Warmuth. Membership for

growing context–sensitive grammars is polynomial. Journal of Computer and System Sciences, 33(3):456–472, 1986.

[GGH69] Seymour Ginsburg, Sheila Greibach, and John E. Hopcroft. Studies in abstract families of languages. Memoirs of the American Mathematical Society, 87:1–51, 1969.

[Gla64] Aleksey Vsevolodovich Gladkii. � ��������� ������ � �����

������� ��������������� ������������. ������� � �������

�������, 3(5-6):29–44, 1964. English title: On the complexity of derivations in context-sensitive grammars; journal: Algebra and Logics, Seminar, Academy of Sciences of USSR, Novosibirsk.

[Har78] Michael A. Harrison. Introduction to Formal Language Theory. Series in Computer Science. Addison-Wesley, Reading, MA, 1978.

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

[Jan79] Matthias Jantzen. A remark on increasing grammars. Unpublished note: the content of this note can be read in [Bun96], 1979.

[Kur64] S.-Y. Kuroda. Classes of languages and linear-bounded automata. Information and Control, 7(2):207–223, 1964.

[Nie92] Gundula Niemann. Die Länge wachsender Grammatiken, die aus quasi wachsenden erzeugt werden. Studienarbeit, Fakultät für Mathematik und Informatik, Universität Würzburg, December 1992. English title: The length of growing grammars that are produced out of quasi-growing ones.

[Nie94] Gundula Niemann. Charakterisierungen mit schwach wachsend kontextsensitiven Grammatiken. Diplomarbeit, Fakultät für Mathematik und Informatik, Universität Würzburg, March 1994. English title: Characterizations with weakly growing context-sensitive grammars.

51 [Nie96] Gundula Niemann. On weakly growing grammars. Technical

Report 155, Fakultät für Mathematik und Informatik, Universität Würzburg, October 1996.

[Pau78] Wolfgang J. Paul. Komplexitätstheorie. Teubner Studienbücher Informatik. B. G. Teubner, Stuttgart, 1978. English title: Complexity Theory.

[Pip79] Nicholas Pippenger. On simultaneous resource bounds. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, Washington, D. C., 1979. Institute of Electrical and Electronics Engineers, IEEE Computer Society Press.

[Rei90] K. Rüdiger Reischuk. Einführung in die Komplexitätstheorie. Leitfäden und Monographien der Informatik. B. G. Teubner, Stuttgart, 1990.

[Ruz80] Walter L. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21(2):218–235, 1980.

[Sal73] Arto Salomaa. Formal Languages. Academic Press, New York, 1973. German translation: [Sal78].

[Sal78] Arto Salomaa. Formale Sprachen. Springer-Verlag, Berlin, Heidelberg, New York, 1978. The English original appeared as [Sal73].

[Sch92] Carmen Schwenkel. Einige komplexitätstheoretische Untersuchungen kontextsensitiver Grammatiken mit Bewertungsfunktionen. Studienarbeit, Fakultät für Mathematik und Informatik, Universität Würzburg, June 1992. English title: Some complexity theoretical investigations of context-sensitive grammars with valuation functions.

[Sch93] Carmen Schwenkel. Eigenschaften schwach wachsend kontextsensitiver Sprachen. Diplomarbeit, Fakultät für Mathematik und Informatik, Universität Würzburg, August 1993. English title: Properties of weakly growing context-sensitive languages.

52 [Smu61] Raymond M. Smullyan. Theory of Formal Systems, volume 47

of Annals of Mathematical Studies. Princeton University Press, Princeton, New Jersey, 1961.

[Sud78] Ivan H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25(3):405–414, 1978.

[Tur36] Alan Mathison Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(2144):230–265, 1936. A correction to this paper appeared in the same periodical, series 2, 43(2198):544–546, 1937.

[vBCMV83] Burchard von Braunmühl, Stephen Cook, Kurt Mehlhorn, and Rutger Verbeek. The recognition of deterministic CFLs in small time and space. Information and Control, 56(1/2):34–51, January/February 1983.

[WW86] Klaus W. Wagner and Gerd Wechsung. Computational Complexity. VEB Deutscher Verlag der Wissenschaften and Reidel Verlag, Berlin, 1986.

53