Weak Growing Context-Sensitive Grammars

Gerhard Buntrock, Gundula Niemann

Report No. 112 Mai 1995

Universität Würzburg, Technical Report

Weak Growing Context-Sensitive Grammars ^{∗}

Gerhard Buntrock and Gundula Niemann

Institut für Informatik Universität Würzburg D-97072 Würzburg, Germany;

        E-mail: [bunt, niemann]@informatik.uni-wuerzburg.de

Mai 1995

Abstract. Well investigated are growing context-sensitive languages (GCSL), i. e. languages defined by grammars that have only growing rules, where the left side of a growing rule is shorter than its right side. GCSL is characterized by quasi growing context-sensitive grammars (QGCSG), i. e. the rules therein are growing only with respect to a valuation of all the strings by a homomorphism to natural numbers with addition.

In this paper we introduce weak growing context-sensitive grammars (WGCSG), i. e. grammars that are growing with a weighted valuation of all strings, where the weights are the values of a position valuation. Here we evaluate a string by summing up every product of a symbol value with its position value.

For every position valuation which does not agree with the beginning of any exponential function, the corresponding class of WGCSGs characterizes CSL, shown by a somehow tricky proof. Such a valuation function is called unsteady. On the other hand all WGCSG related to steady position valuations are linearly inclusion-ordered and characterize the hierarchy of exponential time bounded languages in CSL. This hierarchy collapses iff

• any class defined by an unsteady position valuation has a normal form of order 2 (e. g. Cremers’ or Kuroda’s normal form)

• any class defined by a steady position valuation is closed under inverse homomorphisms.

Introduction

A beautiful theory has always simple concepts and remarkable results. Here we investigate a widely unknown but nice part of the class of context-sensitive languages (CSL).

Our simple concept consists in a valuation of strings and concentration on context-sensitive grammars that are growing under such valuation, and the remarkable results are in form of characterizations of known double bounded complexity classes by this quite different concept. Paul asks in general which kind of speed up theorem does exist for space bounded computations ([Pau78]). Only little is known about such dual bounded classes, see e. g. [Pip79]. Here we characterize the open problem, whether all linear space-bounded automata can be simulated by linear space-bounded automata with an additional universal exponential time bound in the concepts of formal language theory. There it is questioned, whether a class of languages has a normal form of bounded order or whether another class is closed under inverse homomorphisms.

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

Noam Chomsky already has observed in his famous work that CSL is characterized by monotone grammars, that are 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 for definition.

Dahlhaus and Warmuth investigated the complexity of growing context-sensitive languages (GCSL) and found out that GCSL is contained in LOGCFL ([DW86]), the class of such languages that can be transformed into a context-free language (CFL) using logarithmic space ([Sud78], [Ruz80]). Note, that LOGCFL is a subclass of P. GCSL is defined with growing context-sensitive grammars (GCSG), that is done by replacing “as least as long as” in the definition of CSG by “longer than” ^{1}. 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 grammars (quasi GCSG, QGCSG for short) characterizes GCSL ([BL92], [BL94]).

Unfortunately, the class GCSL is very weak. Not even the language COPY := {ww | w ∈ {a, b}^{∗}} is contained in GCSL ([Bun93], see also [BO95]).

Weak growing context-sensitive grammars (WGCSG) are a generalization of QGCSG. In a WGCSG we valuate the symbols as well as the positions 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 context-sensitive grammar is called weak 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 side is lower than the one of the right side. (This is defined precisely in Def. 1.2.) The weak 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 symbols by a rule. This can be used to prove COPY ∈ WGCSL_{s} for any non-constant 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 any position valuation s.

For important language classes we expect some essential closure properties; 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. With standard arguments the following can be proved: for any 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 any position valuation s. What is missing (e. g. to be an abstract family of languages) is the closure under inverse homomorphism and the one under k-bounded homomorphism, where from [GGH69] it is known that, if the one holds, then also the other and vice versa because of the closure properties we already know. The closure under inverse homomorphism here can neither be shown nor negated; a main result in this context is the equivalence of this problem to the problem whether all linear space-bounded automata can be simulated by linear spacebounded automata with an additional universal exponential time bound. The reason for this equivalence lies in the fact that for any non-constant position valuation the closure under inverse homomorphism of WGCSL_{s} equals CSL. To prove these results we distinguish steady and unsteady position valuations: A position valuation is steady, if it agrees with the beginning 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 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 weak 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 to WGCSLs. On the other hand for every language that can be recognized by a linear space-bounded automaton exists a steady position valuation s such that this language belongs to WGCSL_{s}. To get here a very tight relation, we introduce a new type of counters: grammars that count. Furthermore, the weak growing context-sensitive languages corresponding to different growth factors build up a linearly inclusion-ordered hierarchy that characterizes the exponential time hierarchy for CSL. For unsteady position valuations an infinite extension in a way that the value of a sentential form increases if and only if a weak growing context-sensitive rule is applied does not exist. Here we will show that arbitrary long derivations are possible. We interpret this to be the reason for the outcome that for every unsteady position valuation the corresponding class of weak growing context-sensitive grammars characterizes CSL. Another important difference for the steady and unsteady cases consists in the existence of normal forms of order 2. Note, every s-weak growing context-sensitive grammar in a normal form of order 2 is a weak growing context-sensitive grammar related to a steady position valuation. Here we know that for every steady position valuation and every weak growing context-sensitive grammar related to it there exists a normal form. For this we will use Cremers’ normal form, which has the advantage that it has a minimal number of different types of rules. Additionally it turns out that the growth factor of a steady position valuation characterizes a weak 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 natural algorithm to reduce the order of a rule and similar ones do not work.

1Note we differ between the name of the class CSG and a member CSG

Thus we obtain the equivalence of the following problems

• Does the exponential time hierarchie 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 weak growing context-sensitive languages coincides with CSL?

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

• Does there exist an unsteady position valuation such that the following holds: Any weak growing context-sensitive grammar related to this position valuation can be transformed into an equivalent one in an order-2-normal form that is weak growing context-sensitive related to any position valuation?

1 Preliminaries

A context-sensitive grammar (CSG) is a quadruple ⟨N, T, S, P ⟩, where N and T are finite disjoint alphabets of nonterminal and terminal symbols, respectively, S ∈ N is a 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 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, 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 = ⟨N, T, S, P ⟩ is described by: L(G) = {w ∈ T^{∗} | S ⟹^{∗}_{G} w}. Grammars with α ∈ N for each rule (α → β) ∈ P are called context-free. The corresponding language class is denoted by CFL. By replacing the inequality in the definition of context-sensitive grammars by a sharp one, 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 like we did above we can associate them with a certain value (or weight). A grammar G = ⟨N, T, S, P ⟩ is called quasi growing context-sensitive, if it is contextsensitive and there exists a function f: N ∪ T → IN such that for each rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P holds:

∑_{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 symbol valuation for G.

If in the definition above we do without the context-sensitivity, but continue demanding that if (S → ε) ∈ P, S does not appear on the right side of any rule, we obtain the quasi growing grammars, and the set of all such grammars is denoted by QGG.

In [BL92] and [BL94] it was shown that both quasi growing grammars 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 position inside a rule. A position valuation must valuate at least one position and it must be unbroken, because otherwise the valuation of a rule could not be defined naturally. In the following we will refer to max {max {|α|, |β|} | (α → β) ∈ P } as the order of G.

Definition 1.1 A position valuation is a function s: IN^{+} → IN^{+} with:

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

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

It is also possible to allow zero points for position valuations, but with the techniques used to show our main results we get for any position valuation with zero points a characterization of CSL.

We restrict ourselves to the most interesting position valuations which have at least two valuated positions.

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

(i) G is context-sensitive

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

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

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

Such a function f is called symbol valuation for G. If the inequality applies for a rule (α → β) ∈ P, we say it is s-weak 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 position inside a rule, it is possible to interchange two symbols by a rule. This can be used to show that the language COPY := {ww | w ∈ {a, b}^{∗}} is weak growing context-sensitive related to any non-constant position valuation. To give an intuition of weak growing context-sensitive grammars, we look at this example closely:

Example 1.3 We look at the language COPY := {ww | w ∈ {a, b}^{∗}}. Let s be 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:

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

and P consisting of the following rules:

\begin{matrix}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 \end{matrix}

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

\begin{matrix}f(S) = f(A) = f(B) = f((X, a)) = f((X, b)) = 1 \\ f(A′) = f(B′) = 2, f(a) = f(b) = 2 \end{matrix}

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

As COPY ∉ GCSL is true ([Bun93]), we have WGCSL_{s} ⊈ GCSL for any non-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, if we use classical context-sensitive grammars in the definition of WGCSGs, we get a subclass of GCSG ([Nie94a]). Here the interesting question arises whether this type 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 any position valuation s.

We now look briefly at some robustness properties of the definition of weak growing context-sensitive languages:

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

Proposition 1.4 In a WGCSG related to a position valuation s we can delete chain rules, even if there is only a symbol valuation such that some chain rules are not strictly growing, i.e. cycling with chain rules can be deleted in such cases.

Furthermore terminals can be forbidden for the left side of rules.

As in an inequality the multiplication of both sides with the same positive value does not effect its validity, the following holds:

Proposition 1.5 For all k ∈ IN^{+} the classes WGCSL_{k·s} are the same. The same holds for k ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+}.

Thus for any constant position valuation C holds WGCSG_{C} = QGCSG and consequently WGCSL_{C} = GCSL.

The values can not only be stretched but also moved, which leads to the following result:

Proposition 1.6 In Definition 1.2(iii) it is sufficient to demand that there exists a function with values in Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} that fulfills the property (∗).

Proof: Let s be a position valuation and let G = ⟨N, T, S, P ⟩ be a context-sensitive grammar where s has at least ord(G) valuated positions. Let f: N ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} be a symbol valuation such that for every rule (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P holds

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

Let N ∪ T =: \{a_{1}, …, a_{k}\} and f(a_{i}) = \frac{p_{i}}{q_{i}} with p_{i} ∈ ZZ and q_{i} ∈ IN for i = 1, …, k. With an easy transformation we obtain a symbol valuation with symbols in IN: Let q := lcm(q_{1}, …, q_{k}) the common denominator of all values and z := q · | min{0, q_{1}, …, q_{k}}| 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}) := q · f(a_{i}) + z. The inequalities still apply, as the grammar has no length-decreasing rules. ♣

In a similar way it can be seen that allowing values out of Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+} for position valuations does not lead to any new language classes.

As we mentioned above, in the case of quasi growing context-sensitive grammars if we do without context-sensitivity we obtain grammars that characterize the same language class ([BL92]). In the case of weak growing context-sensitive grammars the effect is different: If in Definition 1.2 we leave out the demanding of context-sensitivity, we obtain the quasi weak growing grammars, which already characterize the languages generated by general grammars ([Nie94b]), i. e. the class of recursively enumerable sets.

2 Closure and Normal Form

2.1 Closure Properties

To come to know a new language class more closely, it is useful to learn something 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 any position valuation s, i. e. WGCSL_{s} is a basis for r. e. sets.

With standard arguments it can be shown:

Theorem 2.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.

Additionally it can be shown:

Theorem 2.2 Let s be a non-constant position valuation. Then WGCSL_{s} is closed under transposition.

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

For a grammar G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} a grammar G̃ = ⟨Ñ, T, S̃, P̃⟩ is constructed as follows:

Ñ = N ∪ {S̃} ∪ {a′ | a ∈ T } ∪ {(M, X) | X ∈ N} ∪ {(M, a′) | a ∈ T }

and the rules in P̃ are to realize the following:

First for a word w = w_{1} … w_{n} ∈ L the sentential form (M, 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

(M, a′)b′ → (M, b′)a
ab′ → b′a
(M, a′) → a

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

Clearly L(G̃) = L(G)^{T}. Out of a symbol valuation for G an appropriate one for G̃ can be constructed.

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

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

In order to show that WGCSL_{s} is an AFL for a certain position valuation s we would have to show that WGCSL_{s} is closed under inverse homomorphism (or under k-bounded homomorphism because of Theorem 2.1 and [GGH69]).

It turns out that for steady position valuations this problem is equivalent to the problem whether all linear space-bounded automata can be simulated by linear space-bounded automata with an additional universal exponential time bound (see Theorem 5.5). The reason for this equivalence lies in the fact that for any position valuation the closure under inverse homomorphisms of WGCSL_{s} equals CSL (see Theorems 3.4 and 5.4).

2.2 Normal Form

To get our main results we now introduce the two cases of steady and unsteady position valuations, and first we work out what we can say about the transformability of corresponding weak growing context-sensitive grammars into an order-2-normal form.

Definition 2.3 A position valuation s: IN^{+} → IN^{+} is called steady, if it agrees with the beginning part of an exponential function, that is, if it can be written as

s(i) = s(1) · w(s)^{i−1} where w(s) ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+}, and w(s) = \frac{s(2)}{s(1)} ;

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 s has at least 3 valuated positions and if there exists a valuated position i ∈ IN^{+} 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.

For every steady position valuation s any grammar in WGCSG_{s} can be transformed into a normal form of order 2. We will use the Cremers’ normal form ([Cre73]). Compared with all other normal forms of order 2, the advantage of Cremers’ normal form consists in the fact that it has a minimal number of different types of rules. Moreover, with the probably more popular normal form proposed by Kuroda we can only describe classical context-sensitive grammars, which leads here to a language class contained in GCSL, as we mentioned in Section 1.

Definition 2.4 [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, A → a, where A, B, C, D ∈ N, a ∈ T.

At first we adapt the natural algorithm to reduce the order of a grammar.

Theorem 2.5 Let s be a steady position valuation. Then for every grammar G ∈ WGCSG_{s} of the order ℓ ≥ 3 exists an equivalent grammar G′ ∈ WGCSG_{s} of the order ℓ − 1.

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

We now construct a grammar G′ = ⟨N′, T, S′, P′⟩ and a symbol valuation f′: N′ ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 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 repeat the following:

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

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

6. Define the rules

\begin{matrix}(R1) & α_{1}α_{2} → β_{1}X \\ (R2) & Xα_{3} … α_{n} → β_{2} … β_{m} \end{matrix}

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

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

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

It holds L(G′) = L(G). By calculation and Proposition 1.6 can be shown G′ ∈ WGCSG_{s′}. By Proposition 1.5 this implies G′ ∈ WGCSG_{s} (since s(i) = w(s) · s′(i) for every i ∈ IN^{+}).

♣

For unsteady position valuations this algorithm and similar ones do not work. This can be checked looking at the following interesting example.

Example 2.6 Let s = id, i. e. s(i) = i for every i ∈ IN^{+}, 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, f(β_{3}) = 1

Then the rule is id-weak growing with f, and in the rules α_{1}α_{2} → β_{1}X and Xα_{3} → β_{2}β_{3} the symbol X can not be valuated appropriately.

Theorem 2.5 can be applied step by step:

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

Remark: Thus for a steady position valuation s the class WGCSL_{s} is characterized by the growth factor w(s) (this follows from Theorem 2.7 and Proposition 1.5). So we introduce the following notion:

WGCSL_{w(s)} := WGCSL_{s}

So when we treat steady position valuations we can assume without loss of generality that s is 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 2.8 Let s be a steady position valuation. Then

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

Proof: Let s be a steady position valuation and G = ⟨N, T, S, P ⟩ ∈ WGCSL_{s} = WGCSL_{\frac{s(2)}{s(1)}} in Cremers normal form (Theorem 2.7), and let f be a symbol valuation

for G. We just describe the construction of a grammar G′ = ⟨N′, T, S, P′⟩ ∈ WGCSG_{\frac{s(1)}{s(2)}}

that generates L(G)^{T}. Then the claims of the theorem can be concluded easily with Theorem 2.2.

The length preserving rules are just transposed. Now we look at the expanding rules. In a derivation generating a word w there can (at most) |w| expanding rules be used. With every use of an expanding rule a new symbol is generated. Thus, in the transposed version of an expanding rule we append an encoded weight to the new symbol such that the resulting rule becomes s-weak growing with respect to an appropriate extension of f|_{N}. In further rules this appended encoded weight just continues to be glued (at the same position inside a rule). That means, corresponding copies of all other rules are put into P′, too. In the terminal rules those appended encoded weights are swallowed (by defining the symbol values of the terminals appropriately). ♣

3 The Unsteady Position Valuation

In this section it turns out that WGCSL_{s} = CSL for any unsteady position valuation s. The only inclusion we have to show is CSL ⊆ WGCSL_{s}.

It is well known that linear bounded automata characterize the context-sensitive languages ([Kur64]). This will be used extensively when we show the claim mentioned above. There the following technique for simulating a linear bounded automaton by a context-sensitive grammar is adapted (see e. g. [Har78]): We use a linear bounded automaton that has a single tape, writes 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. [Har78], [HU79], [Tur36]). Each configuration is represented by a certain sentential form (see Fig. 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.

…  … 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)

This sentential form is generated with the initial configuration with any 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.

In the other way, simulating a context-sensitive grammar by a linear bounded automaton we just follow a derivation step by step and compare the derived word with the input afterwards.

As we mentioned before, for any unsteady position valuation holds WGCSL_{s} = CSL. To prove this, we use that every unsteady position valuation s has a blip (see Definition 2.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 a beginning part up to the position j + 1

(iv) s is monotone decreasing on a beginning 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 construction for an s-weak growing context-sensitive grammar analogously to the algorithm mentioned above.

To the first case (i):

The “valley blip” in the position valuation is used like follows: All nonterminal symbols that represent simple tape cells are valuated (by an appropriately defined symbol valuation) with the same value, and the nonterminal symbols to which a state is added are valuated with a greater value. In a rule that simulates a step of the linear bounded automaton, the state “moves” following the move of the automaton’s head. Thus, the additional weight (corresponding to the state) also “moves”, and by an appropriate left context the rule is constructed such that on the left side the state is positioned exactly on that blip. Since the positions to the right and to the left of this one are both valuated higher, the rule becomes s-weak growing with the symbol valuation mentioned above.

With Figure 2 this is illustrated.

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

Figure 2: Simulation in the first case (sketch)

To continue working there must exist several symbols in the sentential form on both sides of the state: to the right at least one, to the left at least j − 1. Therefore at the borders several steps must be condensed, because the state must not be placed in a border symbol in the sentential form since no s-weak growing rule can be built that moves the state out of such a position.

To the second case (ii):

In the case of a “peak blip” we can use the same algorithm as we used in the first case. We just have to redefine the symbol valuation such that the nonterminals representing simple tape cells are valuated higher than the ones containing a state.

To the third case (iii):

Concerning a monotone increasing position valuation (up to the position j + 1) we relate the state with a greater value (than the simple tape cells) for moving right and with a lower one for moving left. To do this we mark the state with the direction it moved to the last time. With a reversal (change of direction of the move) this value has to be changed. It is no problem in a weak growing grammar to change from a lower to a greater value. But in 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 besides the point of reversal. From there it is hiking to the right to be swallowed.

This is illustrated in Figure 3.

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

in the sentential form then should happen the following:

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

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

Figure 3: Simulation with swallower

It is no problem to let the “surplus weight” (encoded in the star ⋆) hike to the right.

We now introduce a swallower, that is a string θ together with some rules that can be integrated into a given s-weak growing context-sensitive grammar G such that any 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 3.1 Let s be an unsteady position valuation which is monotone increasing on a beginning part up to its first blip, let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Define a quintuple S = (N_{1}, N_{2}, N_{swallow}, θ, P_{swallow}) where 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)^{∗}. S_{s} is a swallower for s and G, or shorter an s-swallower for G, if the following holds:

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

– f is a symbol valuation for G, i. e. every rule in P is s-weak growing with f – every rule in P_{swallow} is s-weak growing with f

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

• there exists an l ∈ IN such that for every w ∈ (N ∪ T)^{∗} with |w| ≥ l and for every

X ∈ N_{1}, Y ∈ N_{2} holds: wY θ ⟹^{∗}_{P_{swallow}} wXθ.

If N_{swallow} ⊆ N and P_{swallow} ⊆ P, we also call S_{s} an s-swallower in G.

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

Example 3.2 Take the unsteady position valuation id defined by id(i) = i for every i ∈ IN^{+}. Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{id} with {X, Y } ∈ N and let f be a symbol valuation for G with f(X) = 1, f(Y) = 2.

Define S = (N_{1}, N_{2}, N_{swallow}, θ, P_{swallow}) with N_{1} = {X}, N_{2} = {Y }, N_{swallow} = {X, Y, M, [⋆], A, B, V }, θ = MAV, and a set of rules P_{swallow} = {(R1), (R2), (R3)} where:

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

Using this 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:

\begin{matrix}f(M) = 1, & f([⋆]) = 2, \\ f(A) = 1, & f(B) = 8, & f(V) = 5 \end{matrix}

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

for (R1) : 1 · 2 + 2 · 1 = 4 < 1 · 1 + 2 · 2 = 5 for (R2) : 1 · 2 + 2 · 1 + 3 · 5 = 19 < 1 · 1 + 2 · 8 + 3 · 1 = 20 for (R3) : 1 · 8 + 2 · 1 = 10 < 1 · 1 + 2 · 5 = 11 Thus, these rule are id-weak growing with f.

In the construction of these rules we exploit that with the position valuation 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 has to 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’s ⌈\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 P_{swallow} swallows a value encoded in the star, and S_{s} is an s-swallower in G.

Now we turn to the construction of a swallower for any unsteady position valuation that is monotone increasing at least up to a position after the first blip.

Theorem 3.3 Let s be an unsteady position valuation which is monotone increasing 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.

Proof: We just introduce the construction of the swallower 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 f(X) < f(Y) for every X ∈ A_{1}, Y ∈ A_{2}. Define N_{swallow} = {M, [⋆], A, B, V }, θ = MAV, let

l = \{ \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} = {αY M → αX[⋆] | α ∈ (N ∪ T)^{l}, Y ∈ A_{2}, X ∈ A_{1}}
R_{2} = {α[⋆]AV → αMBA | α ∈ (N ∪ T)^{j−2}}
R_{3} = {αMBA → αMAV | α ∈ (N ∪ T)^{j−3}}
P_{swallow} = R_{1} ∪ R_{2} ∪ R_{3}

Note that the length of α in R_{2} and R_{3} is different.

Now we extend the symbol valuation f to N_{swallow} with values in Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} as follows, where μ := max{f(Y) − f(X) | X ∈ N_{1}, Y ∈ N_{2}}:

\begin{aligned}f(M) & := 1,  f([⋆]) := 1 + μ,  f(A) := 1 \\ f(B) & := \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · (s(j − 1) · s(j) · μ + s(j) + s(j + 1)) + 1 \\ f(V) & := \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · ((s(j − 1))^{2} · μ + s(j − 1) + s(j)) + 1 \end{aligned}

It can be checked arithmetically that the rules in P_{swallow} all are s-weak growing with f. (In order to check R_{2} and R_{3} it is helpful to compute first s(j) · f′(B) − s(j + 1) · f′(V) and s(j) · f′(V) − s(j − 1) · f′(B), respectively.) As we have seen in Proposition 1.6, f can be transformed into a symbol valuation with values in IN^{+}.

Thus f is now a symbol valuation for the swallower as well. Let w ∈ (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θ

♣

So we can integrate a swallower into an s-weak growing context-sensitive 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 transformed into terminals and expanded at the same time. Together with the expansion the swallower is swallowed. If s on a beginning part is constant, we have the same conditions for borderhandling as in the first and the second case.

To the fourth case (iv):

Concerning an unsteady position valuation that 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. That means, the “surplus weight” is generated in a left-right-reversal and hikes to the left, where it is swallowed. The swallower also is 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 context of the rules in R_{3}, and the left 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.

Since in all cases (i) – (iv) we can construct an appropriate weak growing context-sensitive grammar we have the following:

Theorem 3.4 For every unsteady position valuation s holds:

WGCSL_{s} = CSL

For a more detailed description see [Nie94a].

4 The Steady Position Valuation

4.1 Efficient Simulation of a Grammar

4.1.1 Connected Grammars

In a simulation of a grammar with a linear bounded automaton, the automaton can follow the derivation step by step, if it is connected (see Definition 4.1), while in a non-connected grammar in every step it has to 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 4.1 Let G = ⟨N, T, S, P ⟩ be a grammar. Let w_{0} = S ⟹ w_{1} ⟹ … ⟹ w_{t} be a derivation in G, let (α_{i} → β_{i}) ∈ P 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.

Gladkii showed, that every grammar (of both types: general and context-sensitive) can be transformed into an equivalent one 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 want to show the same is true for weak growing context-sensitive grammars.

Book’s proof carries over easily when we use that we have Cremers’ normal form and can assume, the position valuation is monotone increasing (see Theorems 2.7 and 2.8).

Theorem 4.2 Let s be a steady strictly monotone increasing position valuation. Then for each grammar G ∈ WGCSG_{s} in Cremers’ normal form 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 one in G.

Proof: Let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} in Cremers’ normal form. Let f be a symbol valuation for G.

Now define a grammar G′ = ⟨N′, T, Ŝ, P′⟩ by N′ = N ∪ {Â | A ∈ N}, that is the old set of nonterminals together with a set of new nonterminals in 1-to-1 correspondence with the old, and the following rules:

\begin{aligned}P_{1} & = \{ÂB → ĈD, AB̂ → ĈD, AB̂ → CD̂ | A, B, C, D ∈ N, (AB → CD) ∈ P \} \\ P_{2} & = \{Â → ĈD, Â → CD̂ | A, C, D ∈ N, (A → CD) ∈ P \} \\ P_{3} & = \{Â → a, ÂX → aX̂ | A, X ∈ N, a ∈ T, (A → a) ∈ P \} \\ P_{4} & = \{ÂB → AB̂ | A, B ∈ N\} \\ P′ & = P_{1} ∪ P_{2} ∪ P_{3} ∪ P_{4} \end{aligned}

Following [Boo69] applies L(G′) = L(G), and G′ is a connected grammar. Now define a symbol valuation f′: N′ ∪ T → IN for G′ by:

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

Then every production in P′ is s-weak growing with f′: Each rule from P grows at least by 1 with respect to f. The factor s(2)^{2} in the definition of f′ causes that this “growth ratio” rises 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 have a closer look at the third rule in P_{1}: Because AB → CD is s-weak growing with f, applies

\begin{aligned}s(1) · f(A) + s(2) · f(B) + 1 & ≤ & s(1) · f(C) + s(2) · f(D) \\ ⇒ 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) \end{aligned}

Thus for the left side of the new rule AB̂ → ĈD holds:

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 applies G′ ∈ WGCSG_{s}. The second claim is true following [Boo69]. ♣

It is possible to use the same idea for other position valuations. We even have connectivity if there is no transformation into Cremers’ normal form known.

4.1.2 Efficient Simulation

When we simulate a derivation with a weak growing context-sensitive grammar related to a steady position valuation by a linear bounded automaton, we use the algorithm of Section 3 and Theorem 4.2. In order to estimate the time-bound for the linear bounded automaton, we estimate the length of the derivation in the weak 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 to valuate arbitrary long sentential forms. With every application of a rule the value of the sentential form increases (at least by one).

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

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

Proof: Let r ∈ P be the rule used in the derivation step u ⟹ v. The growth ratio in that rule is at least 1, we denote it by g. Let us now valuate the whole sentential forms u and v and look at the growth ratio of the derivation step u ⟹_{G} v. We obtain a value that differs from g by a factor at least 1, if r is length preserving, and additionally a summand greater 0, if it is length increasing. As there are no length decreasing rules, this implies the estimation in the theorem. ♣

As we saw in Section 3 in the construction of swallowers, in the case of 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 weak growing rule. And in the other way 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. Therefor we need an estimation for symbol valuations.

Proposition 4.4 Let s be a steady strictly monotone increasing position valuation. Let G = ⟨N, T, S, P ⟩ be an s-weak growing context-sensitive grammar of the order ℓ. Then exists a symbol valuation f for G with max{f(X) | X ∈ N ∪ T } ≤ (w(s))^{ℓ·|N∪T |}.

Now we conclude from Theorem 4.3, Definition 2.3 and Proposition 4.4:

Theorem 4.5 Let s be a steady strictly monotone increasing position valuation. Let G = ⟨N, T, S, P ⟩ be an s-weak growing context-sensitive grammar of the order ℓ, let v ∈ L(G). Then the length of a derivation S ⟹^{∗} v is not greater than

∑_{i=1}^{|v|} s(i) · w(s)^{ℓ·|N∪T |} = w(s)^{ℓ·|N∪T |} · ∑_{i=1}^{|v|} s(1) · w(s)^{i−1} ≤ (w(s))^{|v|} · \frac{(w(s))^{ℓ·|N∪T |}}{w(s) − 1} · s(1)

Now we can estimate the computation time a linear bounded automaton needs to simulate a weak growing context-sensitive grammar related to a steady position valuation using Theorems 2.8 and 4.5. (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 4.6 Let s be a steady non-constant position valuation. Let w = max\{w(s), \frac{1}{w(s)}\}. Then:

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

4.2 Counters

We will introduce a counter as an instrument to lay down encoded weights, consisting of a string and some rules. We will use it in a simulation of a linear bounded automaton by a weak growing context-sensitive grammar. The capacity of the counter used will cause a bound of the number of steps that can be simulated.

Definition 4.7 Let s be a steady strictly monotone increasing position valuation, let G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Define a quintuple Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈IN^{+}}, P_{count}) where^{2} N_{1} and N_{2} are finite subsets of N, N_{count} is a set of nonterminals (not necessarily a subset of N), (z_{n})_{n∈IN^{+}} is a sequence of start strings with z_{n} ∈ N_{count}^{n} for every n ∈ IN^{+}, and P_{count} is a finite subset of (N_{2} · N_{count}^{∗} × N_{1} · N_{count}^{∗}) ∪ (N_{count}^{∗} × N_{count}^{∗}).

Z is a counter for G related to the position valuation s or shorter s-counter for G, if the following is true:

• every rule in P_{count} is length-preserving

• there exists a symbol valuation f: N ∪ N_{count} ∪ T → IN with:

– f is a symbol valuation for G, i. e. every rule in P is s-weak growing with f – every rule in P_{count} is s-weak growing with f

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

f |_{N_{1}∪N_{2}∪N_{count}} is a symbol valuation for Z.

If N_{count} ⊆ N and P_{count} ⊆ P, we also call Z_{s} an s-counter in G.

So the counter counts the weight f(Y) − f(X) by applying an appropriate rule out of N_{2} · N_{count}^{∗} × N_{1} · N_{count}^{∗} (and after that probably 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 like mentioned above on Y z′_{n}, and so on. So to use the counter to count several amounts of weight, we apply corresponding increment rules (which are not in P_{counter}, but will be added to P in order to use the counter in G): The set ρ(Z, f) of increment rules for Z with f is defined by: ρ(Z, f) = {(X → Y) | X ∈ N_{1}, Y ∈ N_{2}}.

As capacity K_{Z}: IN^{+} → IN^{+} of Z we declare the function that relates to every index n, how often an increment rule can be used (and the weight “generated” by it can be handled) starting with a string of the form Xz_{n}, where X ∈ N_{1} and z_{n} is the start string with index (and length) n, where “collecting” of weights is allowed (i. e. using several increment rules directly after another). Formally:

K_{Z}(n) = max_{f symb. val. for Z} {i ∈ IN | ∃M ∈ N_{1} ∃z̃ ∈ N_{count}^{n} ∃k ∈ IN such that (r_{1}, …, r_{k}) ∈ (P_{count} ∪ ρ(Z, f))^{k} is a se- quence of rules with Mz_{n} ⟹_{r_{1}} … ⟹_{r_{k}} Mz̃ and |{j ∈ {1, …, k} | r_{j} ∈ ρ(Z, f)}| = i }

Because the set N is finite and each of the rules is length preserving, the capacity of a counter certainly is well-defined. For every counter Z and every c ∈ IN^{+} there is (for the possibility of “collecting” weights) a counter Z′ with K_{Z′} = c · K_{Z}.

We now check the possible capacity for a counter that follows the algorithm: treat the string as a number to a certain base and add up arithmetically. We look at an example first.

2We preferred the symbol “Z” for counters that abbreviates the German word “Zähler”, as the abbreviation “C” often is used for classes and “C” for constants or constant functions.

Example 4.8 Let s_{2} be the position valuation defined by s_{2}(i) = 2^{i−1} for every i ∈ IN^{+}. Define Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈IN^{+}}, P_{count}) by: N_{1} = {M}, N_{2} = {#}, N_{count} = {[0], [1], [U]}, z_{n} = [0]^{n} for each n ∈ IN^{+} and R consisting of the rules:

\begin{matrix}(1) #[0] → M[1] & (3) [U][0] → [0][1] \\ (2) #[1] → M[U] & (4) [U][1] → [0][U] \end{matrix}

Together with the rule M → #, for every start string z_{n} the following derivation steps are possible in Z:

Mz_{n} = M[0] … [0] ⟹^{∗} M[1][0] … [0] ⟹^{∗} M[U][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]

That seems to be a nice counter with the 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} → IN be a symbol valuation. Then we have:

out of rule (3)  : {1 · f([U]) + 2 · f([0]) < 1 · f([0]) + 2 · f([1]) \atop ⇒ f([U]) − f([1]) < f([1]) − f([0])}

and out of rule (4) : {1 · f([U]) + 2 · f([1]) < 1 · f([0]) + 2 · f([U]) \atop ⇒ f([1]) − f([0]) < f([U]) − f([1])}

Both of these inequalities cannot be fulfilled at the same time. Thus there exists no symbol valuation all rules of P_{count} are s_{2}-weak growing with. This implies that Z is no s_{2}-counter.

The reason is, that in every rule we transport a portion of the weight plus an increment for making the rule weak 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.

Theorem 4.9 Let s be an infinite steady strictly monotone increasing position valuation, let l ∈ IN. Let Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈IN^{+}}, P_{count}) be an s-counter working after the following scheme (where [i] denotes a digit represented by l letters from N_{count}, and M ∈ N_{1}, # ∈ N_{2});

\begin{matrix}(R1) & #[0] → M[1], & [U][0] → [0][1] \\ (R2) & #[i] → M[i + 1], & [U][i] → [0][i + 1] for i = 1, …, i_{max} − 1 \\ (R3) & #[i_{max}] → M[U], & [U][i_{max}] → [0][U] \end{matrix}

that is, Z treats the start string like a number to a certain base (here i_{max} + 1) and increments arithmetically (without collecting weights), where [U] denotes the overflow (representing [0] and a carry at the same time) and i_{max} ∈ IN^{+}. ⟶ Then the counter’s capacity can be estimated by

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

where l is such that w(s)^{l} ≥ 3, and c is a constant defined by Z. That is, i_{max} is bounded, and we estimate the bound.

Proof: Let f be a symbol valuation for Z. Define a function g: N^{l} → IN^{+} by

g(a_{1} … a_{l}) = ∑_{i=1}^{l} s(i) · f(a_{i}), where a_{1}, …, a_{l} ∈ N, that is, g valuates the digits, each

represented by l symbols, by condensing the symbol and the position valuation. Let w denote the growth factor w(s). Then we have

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

and out of rule (R3) : \underbrace{g([U]) − g([0])}_{=:μ} < w^{l} · (g([U]) − g([i_{max}]))

This implies

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

> \underbrace{\frac{1}{w^{l}} · μ + … + \frac{1}{w^{l}} · μ}_{i_{max}+1times}

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

And this implies i_{max} + 1 < w^{l} ⇒ i_{max} = ⌈w^{l} − 2⌉ (which implies w^{l} ≥ 3).

Thus we have a number representation to the base ⌈w^{l} − 1⌉. We can fill up the string with overflows “[U]”, and then no rule is applicable any more. Since in a string of the length n we have ⌊\frac{n}{l}⌋ digits, and we can use the symbols that might not be used in a digit (this occurs if n is not divisible by l) only to collect a constant number of weights, the capacity of the counter can be estimated by:

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

The optimum mentioned in the theorem above can really be reached. We put Theorem 4.10 with the exponent rounded up instead of rounded down because of technical reasons in the use of the theorem.

Theorem 4.10 Let s be an infinite steady strictly monotone increasing position valuation, let l ∈ IN such that w(s)^{l} ≥ 3, let c ∈ IN^{+}. 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 ∈ IN^{+}, n ≥ l

Proof: We define an s-counter Z = (N_{1}, N_{2}, N_{count}, (z_{n})_{n∈IN^{+}}, P_{count}) following the scheme in Theorem 4.9. We will use the symbols that are not used in a digit, which only occurs if n is not divisible by l, to use a “cheated” additional digit in this case. Thus we define: N_{1} = {M}, N_{2} = {#}, N_{count} = {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⟩^{n mod l} for every n ∈ IN. The set P_{count} consists of the following rules (for i = 1, …, i_{max} − 1):

\begin{matrix}(R1) & #D^{l−1}[0] → MD^{l−1}[1], & [U]D^{l−1}[0] → [0]D^{l−1}[1], & [U]⟨0⟩ → [0]⟨1⟩ \\ (R2) & #D^{l−1}[i] → MD^{l−1}[i + 1], & [U]D^{l−1}[i] → [0]D^{l−1}[i + 1], & [U]⟨i⟩ → [0]⟨i + 1⟩ \\ (R3) & #D^{l−1}[i_{max}] → MD^{l−1}[U], & [U]D^{l−1}[i_{max}] → [0]D^{l−1}[U], & [U]⟨i_{max}⟩ → [0]⟨U⟩ \end{matrix}

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

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

It can be checked easily that the given rules all are s-weak growing with f.

The rules in the third column give us the possibility to use a “cheated” additional digit, if l does not divide n. The capacity now is calculated just as in the proof of Theorem

4.9, 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 any c ∈ IN^{+}. ♣

4.3 Simulation of Time-Bounded Linear Automata

The counters introduced in Theorem 4.10 now will be used in a simulation of a timebounded linear bounded automaton instead of the swallower we used in Section 3. Out of the capacity of the counter used, the time-bounds for linear bounded automata that can be managed with this counter result.

Theorem 4.11 Let w ∈ IN^{+}, let q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} with 0 < q < 1.

Then:

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

Proof: We just describe the algorithm how the grammar is constructed for a given w ∈ IN^{+} and a given linear bounded automaton. The construction itself then is straight forward.

Let M be any linear bounded automaton that recognizes its language L(M) in the time c·w^{q·n} with an appropriate c ∈ IN^{+}, and let s be a steady position valuation with w(s) = w.

Similar to the third case (iii) in the proof of Theorem 3.4 we divide the sentential form into two parts: In the left one the step-by-step simulation of the automaton takes place in sentential form (scheme):

\overbrace{[\begin{matrix}LBA - Sim \\ 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 (sketch)

the same manner as in the simulation in the proof mentioned above, except that we use tape compression; in the right one a counter is situated. We choose an appropriate compression factor k such that \frac{k}{k−1} · q < 1, and to this k we

choose the width l of a digit such that ⌈w(s)^{l}⌉ ≥ w(s)^{l·q· \frac{k}{k−1}} + 1 and at the same time

w(s)^{l} ≥ 3. Note that the first expression is equivalent to ⌈w(s)^{l} − 1⌉^{\frac{k−1}{k} · \frac{1}{l}} ≥ w(s)^{q}.

Following Theorem 4.10 we can find an s-counter Z with the capacity K_{Z}(m) ≥ c ·

⌈(w(s))^{l} − 1⌉^{⌈^{\frac{m}{l}}⌉} where m = ⌈\frac{k−1}{k}⌉ · n is the width of the counter used in the simulation for an input of the length n. This implies

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

That means, 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 is swallowed. ♣

This means a gap between Theorem 4.6 and Theorem 4.11. As the construction technique used to build a counter with exponential capacity does not lead further (see Theorem 4.9), to close this gap is a nontrivial problem.

5 Characterizing the Exponential Time Hierarchy of CSL

In the previous sections we had a look on several position valuations, structured and investigated them. Now we want to gain an overview about the different classes of weak growing context-sensitive languages related to different position valuations. For a constant position valuation we obtain the same grammars as if we had no position valuation at all, namely the quasi growing context-sensitive grammars, which characterize GCSL ([BL92], compare Section 1). For any unsteady position valuation we obtain the language class CSL, as we saw in Section 3, and the same holds for position valuations with zero points, as we mentioned before (see Section 1). We give an outline of the proof here:

Theorem 5.1 Let s be a position valuation with zero points. Then:

WGCSL_{s} = CSL Proof: (sketch) It is sufficient to show CSL ∈ WGCSL_{s}. We can assume that there exists a zero point j with s(j + 1) = c ≠ 0, as the definition of WGCSG_{s} implies that s is not constantly 0, WGCSL_{s} is closed under transposition (Theorem 2.2 holds) and Theorem 2.8 can be adapted. Regarding these two positions, the “growth factor” in fact is not defined, but it can be seen as arbitrary large. Thus, we can construct a counter similar to the one in Section 4.2 that counts in an arbitrarily given number representation. (For j ≠ 1 we add a left context of length j − 1 to the rules in the proof of Theorem 4.10, 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 4.11, where we choose q = \frac{1}{2}, k = 2, and b^{2} instead of ⌈w(s) − 1⌉ is the base of the number representation the counter uses. Thus, the linear bounded automaton can be simulated by an s-weak growing context-sensitive grammar. ♣

For every steady position valuation s we saw in Section 2.2 that the corresponding class of weak growing context-sensitive languages is characterized by the growth factor w(s), and in the Theorems 4.6 and 4.11 was shown:

Theorem 5.2 Let s be a steady non-constant position valuation. Define w := max \{w(s), \frac{1}{w(s)}\}. For every q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+}, 0 < q < 1 holds:

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

This implies WGCSL_{w} ⊆ WGCSL_{v} for v ∈ IN^{+}, v > w.

The resulting relations for different growth factors are depicted in Figure 5.

[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

As every polynomial time bound can be exceeded by any exponential time bound, it can be concluded:

Theorem 5.3 For every steady non-constant position valuation s holds:

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

Thus we have all the relations depicted in Figure 6 (p. 27), where we concentrated on some specific classes because of clarity. Thus the weak 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 4.2 and the idea of construction in the proof of Theorem 4.11 it can be shown:

Theorem 5.4 Let s be a steady non-constant position valuation. The closure of WGCSL_{s} under inverse homomorphism [ k-bounded homomorphism ] is CSL.

Proof: Let L ∈ CSL, and let M be a linear bounded automaton that accepts L in the time t · 2^{c·n}. Let Σ be the input alphabet. Analogously to the grammar in the proof of Theorem 4.11 we construct an s-weak growing context-sensitive grammar G that simulates M and uses a counter just like the one we used in the proof we mentioned above. For an input word of length n we choose a start string of the length m for the counter, where m ≥ \frac{l·c}{log(w(s)−1)} · n and l is chosen such that w(s)^{l} ≥ 3. 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}

that 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)}⌉}. Together with the expansion the counter is swallowed.

We define a homomorphism h: Σ^{∗} → (Σ ∪ \{♢\})^{∗} by h(a) = a♢^{⌈\frac{l·c}{log(w(s)^{l}−1)}⌉} for every a ∈ Σ. [ a homomorphism h: (Σ ∪ {♢})^{∗} → Σ^{∗} by h(a) = a for every a ∈ Σ, h(♢) = ε. ] Then h(L) = L(G).

[ Then h is k-bounded for L(G) with k = ⌈\frac{l·c}{log(w(s)^{l}−1)}⌉, and h(L(G)) = L. ] ♣

We point out that s is non-constant, not only because the counter is not 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} under 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.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; CSL = WGCSL_{s} , s unsteady pos. val.; or pos. val. with zero pts; 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 const pos. val.]

Figure 6: The exponential time hierarchy of CSL and the hierarchy of weak growing context-sensitive languages Theorem 5.5 Let w > 1, 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̃ holds:

(∗) For every grammar G ∈ WGCSGs̃ exists a grammar G′ ∈ WGCSG_{s} in Cremers’ normal form with L(G′) = L(G)

d) For a certain unsteady position valuation s̃ holds (∗).

Additionally a) implies:

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

and from this can be concluded:

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

6 Conclusion

We have seen a characterization of CSL by weak growing context-sensitive grammars related to an unsteady position valuation (Section 3) and a characterization of the exponential time hierarchy of CSL by classes of weak growing context-sensitive languages related to steady position valuations (Section 5).

As interesting we consider the question, whether the exponential time hierarchy for linear bounded automata collapses.

Theorem 5.5 means the equivalence of the following problems for a steady position valuation s:

• Does for any s̃-weak growing context-sensitive grammar related to an unsteady position valuation s̃ exist an equivalent one in a normal form of bounded order that is weak growing context-sensitive related to the steady position valuation s?

• Is WGCSL_{s} is closed under inverse homomorphism?

• Does the hierarchy of weak growing context-sensitive language classes corresponding to the different growth factors collapse down to WGCSL_{w(s)}? That is: Do CSL and WGCSL_{s} coincide?

• Does the exponential time hierarchy for CSL collapse down to the level of w(s)^{n}? That is: Do CSL and T –NSPACE-TIME (n, O(w(s)^{n})) coincide?

If in the first question we restrict ourselves on an arbitrary position valuation instead of a steady one, we also have to restrict ourselves on normal forms of order 2 (and thus result in a steady position valuation again). The reason lies in the fact that for any contextsensitive grammar exists an equivalent one of the order 3 that is in WGCSL_{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 glue an encoded weight to every rule such that all the rules become weak growing related to s with an appropriately defined symbol valuation f (this idea is similar to the one in the proof of Theorem 2.2). Then we add rules to let those weights hike to the right and a swallower (compare the third case (iii) in the proof of Theorem 3.4). Thus every step of the original derivation can be simulated by using the corresponding rule of the new grammar, moving the encoded weight to the right and swallowing it.

Because of Theorem 2.7 we know that asking for a normal form of bounded order in the case of a steady position valuation is equivalent to asking for an order-2-normal form.

Remember that our notion of a characterization of a hierarchy by another only means that the one collapses if and only if the other does.

In this context it would be interesting to close the gap between Theorem 4.6 and Theorem 4.11, that is to answer the question:

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

Acknowledgements

We thank Hans-Jörg Burtschick for pointing out a former version of Example 2.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.3, Theorem 2.1, Theorem 2.7 and Theorem 4.4, also the idea to build quasi weak growing grammars), and of her pre-thesis paper [Sch92], also extended (the separation of WGCSG_{s} and CSG in Section 1).

References

[BL92] Gerhard Buntrock and Krzysztof Loryś. On growing context-sensitive languages. In Proceedings of the 19th International Colloquium on Automata, Languages and Programmaing, volume 623 of Lecture Notes of Computer Science, pages 77–88. Springer, 1992.

[BL94] Gerhard Buntrock and Krzysztof Loryś. The variable membership problem: Succinctness versus complexity. In Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science, volume 775 of Lecture Notes of Computer Science, pages 595–606. Springer, 1994.

[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 of Computer Science, pages 313–324. Springer, 1995.

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

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

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

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

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

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

[Gla64] Aleksey Vsevolodovich Gladkii. On the complexity of derivations in contextsensitive grammars. Algebri i Logika Sem., 3:29–44, 1964. In Russian.

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

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

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

[Nie92] Gundula Niemann. The length of growing grammars that were produced out of quasi growing ones. Studienarbeit, Universität Würzburg, December 1992. In German.

[Nie94a] Gundula Niemann. Characterizations with weak growing context-sensitive grammars. Diplomarbeit, Universität Würzburg, March 1994. In German.

[Nie94b] Gundula Niemann. Quasi weak growing grammars characterize the recursive enumerable sets. Manuscript, in German, January 1994.

[Pau78] Wolfgang J. Paul. Komplexitätstheorie. B. G. Teubner, Stuttgart, 1978.

[Pip79] Nicholas Pippenger. On simultaneous resource bounds. In Proc. of 20th Annual Symposium on Foundations of Computer Science, 1979.

[Ruz80] Walter L. Ruzzo. Tree–size bounded alternation. Journal of Computer and System Science, 21:218–235, 1980.

[Sch92] Carmen Schwenkel. Some complexity theoretical investigations of contextsensitive grammars with valuation functions. Studienarbeit, Universität Würzburg, 1992. In German.

[Sch93] Carmen Schwenkel. Properties of weak growing context-sensitive languages. Diplomarbeit, Universität Würzburg, 1993. In German.

[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. Proc. London Mathematical Society, 2:230–265, 1936. A correction to this paper has appeared in the same periodical, 43:544–546 (1937).

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

32 Buntrock and Niemann

Preprint-Reihe

Institut für Informatik Universität Würzburg

Verantwortlich: Die Vorstände des Institutes für Informatik.

[1] K. Wagner. Bounded query classes. Februar 1989.

[2] P. Tran-Gia. Application of the discrete transforms in performance modeling and analysis. Februar 1989.

[3] U. Hertrampf. Relations among mod-classes. Februar 1989.

[4] K. W. Wagner. Number-of-query hierarchies. Februar 1989.

[5] E. W. Allender. A note on the power of threshold circuits. Juli 1989.

[6] P. Tran-Gia und Th. Stock. Approximate performance analysis of the DQDB access protocol. August 1989.

[7] M. Kowaluk und K. W. Wagner. Die Vektor-Sprache: Einfachste Mittel zur kompakten Beschreibung endlicher Objekte. August 1989.

[8] M. Kowaluk und K. W. Wagner. Vektor-Reduzierbarkeit. August 1989.

[9] K. W. Wagner (Herausgeber). 9. Workshop über Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen. November 1989.

[10] R. Gutbrod. A transformation system for chain code picture languages: Properties and algorithms. Januar 1990.

[11] Th. Stock und P. Tran-Gia. A discrete-time analysis of the DQDB access protocol with general input traffic. Februar 1990.

[12] E. W. Allender und U. Hertrampf. On the power of uniform families of constant depth threshold circuits. Februar 1990.

[13] G. Buntrock, L. A. Hemachandra und D. Siefkes. Using inductive counting to simulate nondeterministic computation. April 1990.

[14] F. Hübner. Analysis of a finite capacity a synchronous multiplexer with periodic sources. Juli 1990.

[15] G. Buntrock, C. Damm, U. Hertrampf und C. Meinel. Structure and importance of logspace-MOD-classes. Juli 1990.

[16] H. Gold und P. Tran-Gia. Performance analysis of a batch service queue arising out of manufacturing systems modeling. Juli 1990.

[17] F. Hübner und P. Tran-Gia. Quasi-stationary analysis of a finite capacity asynchronous multiplexer with modulated deterministic input. Juli 1990.

[18] U. Huckenbeck. Complexity and approximation theoretical properties of rational functions which map two intervals into two other ones. August 1990.

[19] P. Tran-Gia. Analysis of polling systems with general input process and finite capacity. August 1990.

[20] C. Friedewald, A. Hieronymus und B. Menzel. WUMPS Würzburger message passing system. Oktober 1990.

[21] R. V. Book. On random oracle separations. November 1990.

[22] Th. Stock. Influences of multiple priorities on DQDB protocol performance. November 1990.

[23] P. Tran-Gia und R. Dittmann. Performance analysis of the CRMA-protocol in high-speed networks. Dezember 1990.

[24] C. Wrathall. Confluence of one-rule Thue systems.

[25] O. Gihr und P. Tran-Gia. A layered description of ATM cell traffic streams and correlation analysis. Januar 1991.

[26] H. Gold und F. Hübner. Multi server batch service systems in push and pull operating mode — a performance comparison. Juni 1991.

34 Buntrock and Niemann

[27] H. Gold und H. Grob. Performance analysis of a batch service system operating in pull mode. Juli 1991.

[28] U. Hertrampf. Locally definable acceptance types—the three valued case. Juli 1991.

[29] U. Hertrampf. Locally definable acceptance types for polynomial time machines. Juli 1991.

[30] Th. Fritsch und W. Mandel. Communication network routing using neural nets – numerical aspects and alternative approaches. Juli 1991.

[31] H. Vollmer und K. W. Wagner. Classes of counting functions and complexity theoretic operators. August 1991.

[32] R. V. Book, J. H. Lutz und K. W. Wagner. On complexity classes and algorithmically random languages. August 1991.

[33] F. Hübner. Queueing analysis of resource dispatching and scheduling in multi-media systems. September 1991.

[34] H. Gold und G. Bleckert. Analysis of a batch service system with two heterogeneous servers. September 1991.

[35] H. Vollmer und K. W. Wagner. Complexity of functions versus complexity of sets. Oktober 1991.

[36] F. Hübner. Discrete-time analysis of the output process of an ATM multiplexer with periodic input. November 1991.

[37] P. Tran-Gia und O. Gropp. Structure and performance of neural nets in broadband system admission control. November 1991.

[38] G. Buntrock und K. Loryś. On growing context-sensitive languages. Januar 1992.

[39] K. W. Wagner. Alternating machines using partially defined “AND” and “OR”. Januar 1992.

[40] F. Hübner und P. Tran-Gia. An analysis of multi-service systems with trunk reservation mechanisms. April 1992.

[41] U. Huckenbeck. On a generalization of the bellman-ford-algorithm for acyclic graphs. Mai 1992.

[42] U. Huckenbeck. Cost-bounded paths in networks of pipes with valves. Mai 1992.

[43] F. Hübner. Autocorrelation and power density spectrum of ATM multiplexer output processes. September 1992.

[44] F. Hübner und M. Ritter. Multi-service broadband systems with CBR and VBR input traffic. Oktober 1992.

[45] M. Mittler und P. Tran-Gia. Performance of a neural net scheduler used in packet switching interconnection networks. Oktober 1992.

[46] M. Kowaluk und K. W. Wagner. Vector language: Simple description of hard instances. Oktober 1992.

[47] B. Menzel und J. Wolff von Gudenberg. Kommentierte Syntaxdiagramme für C++. November 1992.

[48] D. Emme. A kernel for funtion definable classes and its relations to lowness. November 1992.

[49] S. Öhring. On dynamic and modular embeddings into hyper de Bruijn networks. November 1992.

[50] K. Poeck und M. Tins. An intelligent tutoring system for classification problem solving. November 1992.

[51] K. Poeck und F. Puppe. COKE: Efficient solving of complex assignment problems with the proposeand-exchange method. November 1992.

[52] Th. Fritsch, M. Mittler und P. Tran-Gia. Artificial neural net applications in telecommunication systems. Dezember 1992.

[53] H. Vollmer und K. W. Wagner. The complexity of finding middle elements. Januar 1993.

[54] O. Gihr, H. Gold und S. Heilmann. Analysis of machine breakdown models. Januar 1993.

[55] S. Öhring. Optimal dynamic embeddings of arbitrary trees in de Bruijn networks. Februar 1993.

[56] M. Mittler. Analysis of two finite queues coupled by a triggering scheduler. März 1993.

[57] J. Albert, F. Duckstein, M. Lautner und B. Menzel. Message-passing auf transputer-systemen. März 1993.

[58] Th. Stock und P. Tran-Gia. Basic concepts and performance of high-speed protocols. März 1993.

[59] F. Hübner. Dimensioning of a peak cell rate monitor algorithm using discrete-time analysis. März 1993.

[60] G. Buntrock und K. Loryś. The variable membership problem: Succinctness versus complexity. April 1993.

[61] H. Gold und B. Frötschl. Performance analysis of a batch service system working with a combined push/pull control. April 1993.

[62] H. Vollmer. On different reducibility notions for function classes. April 1993.

[63] S. Öhring und S. K. Das. Folded Petersen Cube Networks: New Competitors for the Hyepercubes. Mai 1993.

[64] S. Öhring und S. K. Das. Incomplete Hypercubes: Embeddings of Tree-Related Networks. Mai 1993.

[65] S. Öhring und S. K. Das. Mapping Dynamic Data and Algorithm Structures on Product Networks. Mai 1993.

[66] F. Hübner und P. Tran-Gia. A Discrete-Time Analysis of Cell Spacing in ATM Systems. Juni 1993.

[67] R. Dittmann und F. Hübner. Discrete-Time Analysis of a Cyclic Service System with Gated Limited Service. Juni 1993.

[68] M. Frisch und K. Jucht. Pascalli-P. August 1993.

[69] G. Buntrock. Growing Context-Sensitive Languages and Automata. September 1993.

[70] S. Öhring und S. K. Das. Embeddings of Tree-Related Topologies in Hyper Petersen Networks. Oktober 1993.

[71] S. Öhring und S. K. Das. Optimal Communication Primitives on the Folded Petersen Networks. Oktober 1993.

[72] O. Rose und M. R. Frater. A Comparison of Models for VBR Video Traffic Sources in B-ISDN. Oktober 1993.

[73] M. Mittler und N. Gerlich. Reducing the Variance of Sojourn Times in Queueing Networks with Overtaking. November 1993.

[74] P. Tran-Gia. Discrete-Time Analysis Technique and Application to Usage Parameter Control Modelling in ATM Systems. November 1993.

[75] F. Hübner. Output Process Analysis of the Peak Cell Rate Monitor Algorithm. Januar 1994.

[76] K. Cronauer. A Criterion to Separate Complexity Classes by Oracles. Januar 1994.

[77] M. Ritter. Analysis of the Generic Cell Rate Algorithm Monitoring ON/OFF-Traffic. Januar 1994.

[78] K. Poeck, D. Fensel, D. Landes und J. Angele. Combining KARL and Configurable Role Limiting Methods for Configuring Elevator Systems. Januar 1994.

[79] O. Rose. Approximate Analysis of an ATM Multiplexer with MPEG Video Input. Januar 1994.

[80] A. Schömig. Using Kanban in a Semiconductor Fabrication Environment — a Simulation Study. März 1994.

[81] M. Ritter, S. Kornprobst und F. Hübner. Performance Analysis of Source Policing Architectures in ATM Systems. April 1994.

[82] U. Hertrampf, H. Vollmer und K. W. Wagner. On Balanced vs. Unbalanced Computation Trees. Mai 1994.

[83] M. Mittler und A. Schömig. Entwicklung von ”Due–Date“–Warteschlangendisziplinen zur Optimierung von Produktionssystemen. Mai 1994.

[84] U. Hertrampf. Complexity Classes Defined via k-valued Functions. Juli 1994.

[85] U. Hertrampf. Locally Definable Acceptance: Closure Properties, Associativity, Finiteness. Juli 1994.

[86] O. Rose und M. R. Frater. Delivery of MPEG Video Services over ATM. August 1994.

[87] B. Reinhardt. Kritik von Symptomerkennung in einem Hypertext-Dokument. August 1994.

[88] U. Rothaug, E. Yanenko und K. Leibnitz. Artificial Neural Networks Used for Way Optimization in Multi-Head Systems in Application to Electrical Flying Probe Testers. September 1994.

36 Buntrock and Niemann

[89] U. Hertrampf. Finite Acceptance Type Classes. Oktober 1994.

[90] U. Hertrampf. On Simple Closure Properties of #P. Oktober 1994.

[91] H. Vollmer und K. W. Wagner. Recursion Theoretic Characterizations of Complexity Classes of Counting Functions. November 1994.

[92] U. Hinsberger und R. Kolla. Optimal Technology Mapping for Single Output Cells. November 1994.

[93] W. Nöth und R. Kolla. Optimal Synthesis of Fanoutfree Functions. November 1994.

[94] M. Mittler und R. Müller. Sojourn Time Distribution of the Asymmetric M/M/1//N – System with LCFS-PR Service. November 1994.

[95] M. Ritter. Performance Analysis of the Dual Cell Spacer in ATM Systems. November 1994.

[96] M. Beaudry. Recognition of Nonregular Languages by Finite Groupoids. Dezember 1994.

[97] O. Rose und M. Ritter. A New Approach for the Dimensioning of Policing Functions for MPEG-Video Sources in ATM-Systems. Januar 1995.

[98] T. Dabs und J. Schoof. A Graphical User Interface For Genetic Algorithms. Februar 1995.

[99] M. R. Frater und O. Rose. Cell Loss Analysis of Broadband Switching Systems Carrying VBR Video. Februar 1995.

[100] U. Hertrampf, H. Vollmer und K. W. Wagner. On the Power of Number-Theoretic Operations with Respect to Counting. Januar 1995.

[101] O. Rose. Statistical Properties of MPEG Video Traffic and their Impact on Traffic Modeling in ATM Systems. Februar 1995.

[102] M. Mittler und R. Müller. Moment Approximation in Product Form Queueing Networks. Februar 1995.

[103] D. Rooß und K. W. Wagner. On the Power of Bio-Computers. Februar 1995.

[104] N. Gerlich und M. Tangemann. Towards a Channel Allocation Scheme for SDMA-based Mobile Communication Systems. Februar 1995.

[105] A. Schömig und M. Kahnt. Vergleich zweier Analysemethoden zur Leistungsbewertung von Kanban Systemen. Februar 1995.

[106] M. Mittler, M. Purm und O. Gihr. Set Management: Synchronization of Prefabricated Parts before Assembly. März 1995.

[107] A. Schömig und M. Mittler. Autocorrelation of Cycle Times in Semiconductor Manufacturing Systems. März 1995.

[108] A. Schömig und M. Kahnt. Performance Modelling of Pull Manufacturing Systems with Batch Servers and Assembly-like Structure. März 1995.

[109] M. Mittler, N. Gerlich und A. Schömig. Reducing the Variance of Cycle Times in Semiconductor Manufacturing Systems. April 1995.

[110] A. Schömig und M. Kahnt. A note on the Application of Marie’s Method for Queueing Networks with Batch Servers. April 1995.

[111] F. Puppe, M. Daniel und G. Seidel. Qualifizierende Arbeitsgestaltung mit tutoriellen Expertensystemen für technische Diagnoseaufgaben. April 1995.

[112] G. Buntrock, und G. Niemann. Weak Growing Context-Sensitive Grammars. Mai 1995.

[113] J. García and M. Ritter. Determination of Traffic Parameters for VPs Carrying Delay-Sensitive Traffic. Mai 1995.

[114] M. Ritter. Steady-State Analysis of the Rate-Based Congestion Control Mechanism for ABR Services in ATM Networks. Mai 1995.

[115] H. Graefe. Konzepte für ein zuverlässiges Message-Passing-System auf der Basis von UDP. Mai 1995.

[116] A. Schömig und H. Rau. A Petri Net Approach for the Performance Analysis of Business Processes. Mai 1995.

[117] K. Verbarg. Approximate Center Points in Dense Point Sets. Mai 1995.

[118] K. Tutschku. Recurrent Multilayer Perceptrons for Identification and Control: The Road to Applications. Juni 1995.

[119] U. Rhein-Desel. Eine ”Übersicht“ über medizinische Informationssysteme: Krankenhausinformationssysteme, Patientenaktensysteme und Kritiksysteme. Juli 1995.

[120] O. Rose. Simple and Efficient Models for Variable Bit Rate MPEG Video Traffic. Juli 1995.

[121] A. Schömig. On Transfer Blocking and Minimal Blocking in Serial Manufacturing Systems — The Impact of Buffer Allocation. Juli 1995.