Growing Context-Sensitive Languages and Church-Rosser Languages

Gerhard Buntrock^{1} and Friedrich Otto^{2}

1 Institut für Informatik, Universität, Würzburg,

                     bunt@informatik.uni-wuerzburg.de

2 Fachbereich Mathematik/Informatik, Universität-GH, Kassel,

                   otto@theory.informatik.uni-kassel.de

Abstract. The growing context-sensitive languages (GCSL) are characterized by a nondeterministic machine model, the so-called shrinking two-pushdown automaton (sTPDA). Then the deterministic version of this automaton (sDTPDA) is shown to characterize the class of generalized Church-Rosser languages (GCRL). Finally, we prove that each growing context-sensitive language is accepted in polynomial time by some one-way auxiliary pushdown automaton with a logarithmic space bound (OW-auxPDA[log,poly]). As a consequence the class of (generalized) Church-Rosser languages and the class of context-free languages are incomparable under set inclusion, which verifies a conjecture of Mc-Naughton et al [MNO88].

1 Introduction

It is well-known that the class of context-sensitive languages (CSL) coincides with the nondeterministic space complexity class NSPACE(n), and that there exist context-sensitive languages for which the membership problem is PSPACEcomplete. Thus, in their full generality these languages are too powerful for practical applications. On the other hand, context-free languages (CFL) are not powerful enough to completely describe all the syntactical aspects of a programming language like PASCAL, since some of them are inherently context dependent. There are various alternatives to define classes of languages that are strictly in between CFL and CSL. One approach is based on making the context-free grammars more powerful by adding certain attributes that must be evaluated in order to decide whether a sentence derived from that grammar is considered to be ‘valid’ [Knu68]. Another approach is based on restricting the power of contextsensitive grammars. For example, Gladkij considers context-sensitive grammars with an additional bound on the length of derivations ([Gla64], see also [Boo69]). With a linear time-bound these grammars generate the languages in the class CSL_{lin}, which, however, still contains NP-complete languages [Boo78]. Also these restrictions seem to be rather artificial.

Dahlhaus and Warmuth [DW86] consider ‘growing context-sensitive grammars’, that is, context-sensitive grammars for which each production rule is strictly length-increasing. Obviously, for such a grammar the length of a derivation is bounded from above by the length of the sentence derived. Dahlhaus and Warmuth prove that all growing context-sensitive languages (GCSL), that is, the languages that are generated by growing context-sensitive grammars, have membership problems that are solvable in polynomial time. In fact, GCSL is contained in the class LOGCFL of languages that are logspace-reducible to context-free languages. In addition, GCSL is contained in the uniform circuit complexity class AC^{1}, and hence, for each growing context-sensitive language there exists an efficient parallel algorithm for deciding membership in that language [Ruz80]. In particular, the class GCSL is strictly in between the classes CFL and CSL.

From the definition it might appear that GCSL is not an interesting class of languages, but as shown by Buntrock and Loryś, GCSL is an abstract family of languages [BL92], that is, this class of languages is closed under union, concatenation, iteration, intersection with regular languages, ϵ-free homomorphisms and inverse homomorphisms. Exploiting these closure properties Buntrock and Loryś have characterized the class GCSL by various other classes of grammars that are less restricted [BL92].

Using these grammars we characterize the class GCSL by a nondeterministic machine model. The basis of this model is the nondeterministic pushdown automaton with two pushdown stores (TPDA). Several variants of this machine model have been investigated [Wal70, GH68, Boo82]. We have found that the variant, where the input is provided as the initial contents of one of the pushdown stores, is most appropriate for our purposes. Since in full generality this model is equivalent to the Turing machine, we place an additional restriction on it. We assign a positive weight to each tape symbol and each internal state symbol of the machine. By adding up the weights this gives a weight for each configuration. Now we require that the weight of the actual configuration strictly decreases with each step of the TPDA. In this way we obtain the so-called shrinking TPDA. Our first main result states that a language is growing context-sensitive if and only if it is accepted by some shrinking TPDA.

Since the TPDA is a nondeterministic device, it is only natural to ask what class of languages is characterized by the deterministic variant of the shrinking TPDA. The languages accepted by them could be called ‘deterministic growing context-sensitive languages’, but we have chosen a different name based on another characterization for this class of languages. In [MNO88] McNaughton, Narendran and Otto define the concept of a Church-Rosser language (CRL). Essentially, a language is a Church-Rosser language if it consists of all the ancestors of a special symbol with respect to a finite, length-reducing, and confluent string-rewriting system (see Section 4 for the exact definitions). String-rewriting systems are a classical means for investigating formal languages and congruence relations over finite alphabets. Of particular interest are those string-rewriting systems that are noetherian and confluent. Here a system is called noetherian if it does not admit infinite sequences of reductions. Examples are systems that are length-reducing or weight-reducing. It is called confluent if it satisfies the confluence property for all strings (see Section 4). Systems that are both noetherian and confluent are of interest, since they define unique normal forms for all their congruence classes (see [BO93] for a thorough discussion of these topics). In [Boo82] a deterministic TPDA is presented that, on input string w, computes the irreducible descendant (that is, the normal form) of w with respect to a noetherian and confluent string-rewriting system. In general, this deterministic TPDA is not shrinking, but if the underlying string-rewriting system is length-reducing, then it is. Based on this observation we prove that each CRL is accepted by a shrinking deterministic TPDA. Unfortunately, it is not at all clear whether all the languages accepted by these machines are indeed Church-Rosser languages. However, by admitting finite, weight-reducing, and confluent string-rewriting systems we arrive at the concept of a generalized Church-Rosser language (GCRL), and our second main result states that a language is accepted by a shrinking deterministic TPDA if and only if it is a GCRL. This establishes an unexpectedly close relationship between the growing context-sensitive languages and the (generalized) Church-Rosser languages.

Finally, we improve upon a result of Dahlhaus and Warmuth mentioned before by showing that each growing context-sensitive language belongs to the class OW-LOGCFL, that is, it is reducible to a context-free language by a one-way logspace reduction. Based on this result we then conclude that the classes of languages GCRL and CFL, and therewith CRL and CFL, are incomparable under set inclusion, thus confirming a conjecture of [MNO88]. This also proves that GCRL is a proper subclass of GCSL, which means that the nondeterministic variant of the shrinking TPDA is strictly more powerful than its deterministic counter part. The paper closes with a short discussion of open problems concerning our results and the language classes considered.

2 Shrinking Two-Pushdown Automata

A function f : Σ → N_{+} is called a weight-function for Σ. The obvious extension of f to Σ^{∗} will also be denoted by f. Now we present the machine model that is central to our investigations. Definition 1. (a) A two-pushdown automaton (TPDA) is a nondeterministic

automaton with two pushdown stores. Formally, it is defined as a 7-tuple M = (Q, Σ, Γ, δ, q_{0}, ⊥, F), where

– Q is the finite set of states,

– Σ is the finite input alphabet,

– Γ is the finite tape alphabet with Γ ⊃ Σ and Γ ∩ Q = ∅,

– q_{0} ∈ Q is the initial state,

– ⊥ ∈ Γ \ Σ is the bottom marker of the pushdown stores,

– F ⊆ Q is the set of final (or accepting) states, and

– δ : Q × Γ × Γ → 2^{Q×Γ^{∗}×Γ^{∗}} is the transition relation, where δ(q, a, b) is a finite set for each triple (q, a, b) ∈ Q × Γ × Γ.

M is a deterministic two-pushdown automaton (DTPDA), if δ is a (partial) function from Q × Γ × Γ into Q × Γ^{∗} × Γ^{∗}.

(b) A configuration of a TPDA M is described as uqv with q ∈ Q and u, v ∈ Γ^{∗}, where u is the contents of the first pushdown store with the first letter of u at the bottom and the last letter of u at the top, q is the current state, and v is the contents of the second pushdown store with the last letter of v at the bottom and the first letter of v at the top. M induces a computation relation ⊢_{M}^{∗} on the set of configurations. For an input string w ∈ Σ^{∗}, the corresponding initial configuration is ⊥q_{0}w⊥. M can accept either by empty pushdown stores or by final state:

\begin{aligned}N(M) & := & \{w ∈ Σ^{∗} | ∃q ∈ Q : ⊥q_{0}w⊥ ⊢_{M}^{∗} q\}, \\ L(M) & := & \{w ∈ Σ^{∗} | ∃q ∈ F ∃α ∈ Γ^{∗} : ⊥q_{0}w⊥ ⊢_{M}^{∗} αq\}. \end{aligned}

(c) A (D)TPDA M is called shrinking if there exists a weight-function φ : Q ∪ Γ → N_{+} such that, for all configurations u_{1}q_{1}v_{1} and u_{2}q_{2}v_{2} of M, if u_{1}q_{1}v_{1} ⊢_{M} u_{2}q_{2}v_{2}, then φ(u_{1}q_{1}v_{1}) > φ(u_{2}q_{2}v_{2}). By sTPDA and sDTPDA we denote the corresponding classes of automata. Observe that even when accepting by final state, a TPDA is forced to consume

the input completely. Using standard techniques from automata theory it can be shown that we may require the following property for a (shrinking) (D)TPDA M = (Q, Σ, Γ, δ, q_{0}, ⊥, F): Whenever a pushdown store of M is nonempty, then its contents is of the form u⊥ with u ∈ (Γ \ {⊥})^{∗}, where ⊥ is at the bottom, that is, the special symbol ⊥ can only occur at the bottom of a pushdown store, and no other symbol can occur at that place.

From the definition of the transition relation δ we see that M halts immediately whenever one of its pushdown stores is emptied. Because of the above property this happens if and only if a transition of the form δ(q, a, ⊥) ↦ (q′, α, ε) or δ(q, ⊥, b) ↦ (q′, ε, β) is performed. Thus, it suffices to have a single accepting state q_{f} for M. Further, we have the following result, which is easily proved based on the above remarks. Proposition 2. (a) Let M be a TPDA (sTPDA, DTPDA, sDTPDA). Then there

exists an automaton M′ of the same type such that N(M) = L(M′).

(b) Let M be a TPDA (sTPDA, DTPDA, sDTPDA). Then there exists an automaton M′′ of the same type such that L(M) = N(M′′). Thus, in the following we can always take the notion of acceptance that

is most convenient. If we require that the transition relation δ is a mapping from Q × Γ × Γ to finite subsets of Q × Γ^{∗} × (Γ ∪ {ε}), then we get a variant of the pushdown automaton. Thus, with this additional restriction the TPDA characterizes the context-free languages. In particular, the corresponding version of the DTPDA characterizes the class of deterministic context-free languages. However, due to the extra symbol on the ‘input tape’ this version of the DTPDA is more powerful with respect to the acceptance by empty pushdown than the deterministic pushdown automaton.

3 Growing Context-Sensitive Languages

The class of growing context-sensitive languages (GCSL) is defined by a syntactical restriction on context-sensitive grammars [DW86]. Here we give a characterization of this class in terms of the sTPDA. Definition 3. A grammar is a quadruple G = (N, T, S, P), where N and T are the finite disjoint alphabets of nonterminal and terminal symbols, respectively, S ∈ N is the start symbol, and P is a finite set of productions of the form α → β with α, β ∈ (N ∪ T)^{∗}, where α contains at least one nonterminal symbol.

(a) If |α| ≤ |β| holds for all (α → β) ∈ P, then G is called a context-sensitive grammar (CSG).

(b) The grammar G is a growing context-sensitive grammar (GCSG), if the start symbol S does not appear on the right-hand side of any production of G, and if |α| < |β| holds for all productions (α → β) ∈ P satisfying α ≠ S.

(c) The grammar G is a quasi-growing grammar (QGG) if there exists a weightfunction φ : N ∪ T → N_{+} such that φ(α) < φ(β) for all (α → β) ∈ P.

(d) The grammar G is a quasi-growing context-sensitive grammar (QGCSG), if it is quasi-growing and context-sensitive.

(e) A language L is called context-sensitive (growing context-sensitive), if it is generated by some context-sensitive (growing context-sensitive) grammar. These language classes will be denoted by CSL and GCSL, respectively. The quasi-growing grammars were introduced by Buntrock and Loryś [BL92],

who also derived the following result. Proposition 4. [BL92]. A language is growing context-sensitive if and only if it is generated by a QGG, respectively a QGCSG.

Now we come to the first part of our intended characterization theorem. Theorem 5. If a language L is accepted by some shrinking TPDA, then L is a growing context-sensitive language. Proof. Let M = (Q, Σ, Γ, δ, q_{0}, ⊥, {q_{a}}) be a TPDA such that N(M) = L, and let φ : Q ∪ Γ → N_{+} be a weight-function such that M is shrinking with respect to φ. From M we construct a grammar G = (N, T, S, P) as follows:

– N := (Q \ {q_{0}}) ∪ (Γ \ (Σ ∪ {⊥})) ∪ {S}, where S is a new symbol,

– T := Σ ∪ {q_{0}, ⊥}, and

– P consists of the following rules:

\begin{aligned}S & → & ⊥q⊥ & if & (q′, ε, ε) ∈ δ(q, ⊥, ⊥) \\ αq′β & → & aqb & if & (q′, α, β) ∈ δ(q, a, b) \end{aligned}

for all q ∈ Q and a, b ∈ Γ. Recall that we assume that Q ∩ Γ = ∅.

By induction on the number n of steps in a computation it can now be shown that ⊥q_{0}w⊥ ⊢_{M}^{(n)} αqβ if and only if αqβ ⇒_{G}^{(n)} ⊥q_{0}w⊥. Hence, for all w ∈ Σ^{∗}, w ∈ L = N(M) if and only if ⊥q_{0}w⊥ ⊢_{M}^{∗} q′ for some q′ ∈ Q if and only if S ⇒_{G}^{∗} ⊥q_{0}w⊥ if and only if ⊥q_{0}w⊥ ∈ L(G).

Define a weight-function ψ for G by extending φ to N∪T by taking ψ(S) := 1. Then ψ(α) < ψ(β) for each production (α → β) ∈ P, and so we see that G is a QGG. Thus, the language {⊥q_{0}} · L · {⊥} is growing context-sensitive. Since the class GCSL is closed under bounded homomorphisms [Bun93], this implies that L is in GCSL. ⊓ ⊔

To establish the converse result we need the technical notion of connectivity. A grammar is called connected if each proper derivation is connected, that is, for every two consecutive steps in a proper derivation at least one of the symbols that are replaced in the later step was produced by the former. Gladkij has shown that each context-sensitive grammar can be transformed into an equivalent contextsensitive grammar that is connected [Gla64]. Based on Book’s proof for Gladkij’s result [Boo69] the following technical result can be derived.

Theorem 6. For each quasi-growing context-sensitive grammar G, there exists an equivalent quasi-growing context-sensitive grammar G_{0} that is connected, and that produces every string w ∈ L(G_{0}) strictly from right to left.

Now we are prepared to establish the following converse of Theorem 5.

Theorem 7. Every GCSL is accepted by some sTPDA.

Proof. Let L be a GCSL. By Proposition 4 there exist a QGCSG G = (N, T, S, P) and a weight-function φ : N ∪ T → N_{+} such that L(G) = L, and φ(ℓ) < φ(r) holds for all (ℓ → r) ∈ P. By Theorem 6 we may assume that the grammar G is connected, and that it produces every terminal string w ∈ L strictly from right to left. We can even assume that N = N′ ∪ N̂, where N′ ∩ N̂ = ∅, and that each sentential form contains a single symbol from N̂.

Based on this particular grammar, a TPDA M with a single state q can be constructed that, when given a string w ∈ T^{∗} as input, tries to simulate a connected derivation Ŝ ⇒^{∗} w in the reverse order. Hence, for all w ∈ T^{∗}, Ŝ ⇒^{∗} w if and only if ⊥qw⊥ ⊢_{M}^{∗} ⊥q⊥ ⊢_{M} q. Thus, L = N(M). By taking φ(⊥) := φ(q) := 1, φ is extended to a weight function for M. ⊓ ⊔

We can summarize the results of this section as follows.

Corollary 8. A language is growing context-sensitive if and only if it is accepted by some sTPDA.

It is immediate from the definition that each sTPDA is linearly time-bounded, and it accepts a language from P. In Definition 3, if we only require that the weight of the actual configuration does not increase in any step, then we obtain the so-called non-strictly shrinking TPDA. Such an automaton will in general not be linearly time-bounded. However, with an additional linear time-bound this type of automaton characterizes Gladkij’s class CSL_{lin} [Gla64], which contains NP-complete languages [Boo78]. It is an open problem whether the linearly timebounded TPDA that are not required to be non-strictly shrinking accept the same class of languages [Boo69]. Observe that all these classes are proper subclasses of Q, the set of languages accepted by non-deterministic Turing machines in linear time [Boo69, WW86].

4 Generalized Church-Rosser Languages

Now we consider the class of languages that is characterized by the shrinking deterministic TPDA. We give a characterization of this class in terms of certain restricted string-rewriting systems leading to the notion of generalized Church-Rosser languages.

String-rewriting systems form a special class of term-rewriting systems, and as such they have been investigated extensively. Here we just restate a few basic facts that we need in this paper. As our main reference on string-rewriting systems we use the monograph by Book and Otto [BO93], where the various aspects of string-rewriting systems are discussed in detail, and where references to the original literature can be found.

Definition 9. Let R ⊆ Σ^{∗} × Σ^{∗} be a finite string-rewriting system. By →_{R} we denote the single-step reduction relation on Σ^{∗} that is induced by R. The reflexive transitive closure →_{R}^{∗} of →_{R} is the corresponding reduction relation, and the reflexive, symmetric, and transitive closure ↔_{R}^{∗} is the Thue congruence generated by R. The system R is called

– length-reducing if |ℓ| > |r| holds for each rule (ℓ → r) ∈ R,

– weight-reducing if there exists a weight-function f : Σ → N_{+} such that f(ℓ) > f(r) holds for each rule (ℓ → r) ∈ R,

– confluent if u →_{R}^{∗} v and u →_{R}^{∗} w imply that v →_{R}^{∗} z and w →_{R}^{∗} z for some z ∈ Σ^{∗},

– normalized if r ∈ IRR(R) and ℓ ∈ IRR(R \ {ℓ → r}) hold for each rule (ℓ → r) ∈ R, where IRR(R) denotes the set of strings that are irreducible with respect to R, that is, w ∈ IRR(R) if and only if w does not contain the left-hand side ℓ of any rule (ℓ → r) ∈ R as a factor.

If R is a finite string-rewriting system, then IRR(R) is a regular language, and from R a deterministic finite-state acceptor (DFA) can be constructed in polynomial time for the set IRR(R).

If a string-rewriting system R is weight-reducing and confluent, then each congruence class [u]_{R} := {w ∈ Σ^{∗} | u ↔_{R}^{∗} w} contains a unique irreducible string u_{0}, which can then serve as a normal form for this class. For each w ∈ [u]_{R}, w →_{R}^{∗} u_{0}, and given a string u ∈ Σ^{∗}, its normal form u_{0} can be determined in linear time.

Finally, if R is a length-reducing or a weight-reducing string-rewriting system that is also confluent, then one can construct a confluent system R_{0} that is length-reducing or weight-reducing, respectively, in polynomial time from R such that R and R_{0} are equivalent, that is, ↔_{R}^{∗} = ↔_{R_{0}}^{∗}, and, in addition, R_{0} is normalized. Thus, in the following we will restrict our attention to length-reducing, respectively weight-reducing, confluent systems that are normalized.

In [MNO88] the notion of Church-Rosser languages is introduced.

Definition 10. A language L ⊆ Σ^{∗} is a Church-Rosser language (CRL), respectively a generalized Church-Rosser language (GCRL), if there exist an alphabet Γ ⊃ Σ, a finite length-reducing, respectively weight-reducing, confluent stringrewriting system R on Γ, two strings t_{1}, t_{2} ∈ (Γ \ Σ)^{∗} ∩ IRR(R) and a letter Y ∈ (Γ \ Σ) ∩ IRR(R) such that, for all w ∈ Σ^{∗}, t_{1}wt_{2} →_{R}^{∗} Y if and only if w ∈ L.

We claim that the class of generalized Church-Rosser languages coincides with the class of languages that are accepted by sDTPDA. The first half of this result is easily established.

Theorem 11. If a language L is accepted by some sDTPDA, then L is a GCRL.

Proof. Let L be accepted by the sDTPDA M = (Q, Σ, Γ, δ, q_{0}, ⊥, {q_{f}}) with weight-function g, that is, L = L(M). We claim that L is a GCRL.

Let Δ := Q ∪ Γ ∪ Γ̄, where Γ̄ is a new alphabet in 1-to-1 correspondence with Γ. We assume that the three sets Q, Γ, and Γ̄ are pairwise disjoint. The weight-function g is extended to Δ by taking g(ā) := g(a) for all a ∈ Γ. Further, define t_{1} := ¯⊥q_{0} and t_{2} := ⊥. It remains to define a finite string-rewriting system R on Δ. Let R be the system that contains the following rules:

āqb → ūq′v if δ(q, a, b) = (q′, u, v), q ∈ Q, a, b ∈ Γ,
āq_{f} → q_{f}  for all ā ∈ Γ̄.

Here ^{−} : Γ^{∗} → Γ̄^{∗} denotes the obvious isomorphism.

It is immediate that R is a weight-reducing system. Since M is deterministic, there are no overlaps between left-hand sides of rules of R, and so R is confluent. Also t_{1}, t_{2}, and q_{f} are irreducible with respect to R. Since, for all w ∈ Σ^{∗}, w ∈ L if and only if t_{1}wt_{2} = ¯⊥q_{0}w⊥ →_{R}^{∗} ¯⊥ᾱq_{f} →_{R}^{∗} q_{f}, R, t_{1}, t_{2} and q_{f} witness the fact that L is a GCRL. ⊓ ⊔

To show the converse result we need some preparations.

Definition 12. Let R be a string-rewriting system on Σ. A reduction w →_{R} z is called leftmost, denoted w _{L} →_{R} z, if the following condition is satisfied: if w = x_{1}ℓ_{1}y_{1}, z = x_{1}r_{1}y_{1}, and (ℓ_{1} → r_{1}) ∈ R, and also w = x_{2}ℓ_{2}y_{2} for some rule (ℓ_{2} → r_{2}) ∈ R, then x_{1}ℓ_{1} is a proper prefix of x_{2}ℓ_{2}, or x_{1}ℓ_{1} = x_{2}ℓ_{2} and x_{1} is a proper prefix of x_{2}, or x_{1} = x_{2} and ℓ_{1} = ℓ_{2}. Let _{L}→_{R}^{∗} denote the reflexive transitive closure of _{L}→_{R}. For every w, z ∈ Σ^{∗}, a sequence of reductions that begins with w and ends with z such that every step is leftmost is called a leftmost reduction from w to z.

If the system R is normalized, then, for each w ∉ IRR(R), there exists a unique z ∈ Σ^{∗} such that w _{L}→_{R} z. Hence, for normalized systems the process of leftmost reduction is deterministic. In particular, if R is normalized and confluent, then for each w ∉ IRR(R), there is a unique leftmost reduction from w to its normal form w_{0} ∈ IRR(R).

In [Boo82] a DTPDA is described that, given a string w ∈ Σ^{∗} as input, computes a leftmost reduction from w to w_{0} ∈ IRR(R). By modifying this DTPDA appropriately, and by choosing a suitable weight-function the following technical result can be established.

Theorem 13. Let R be a finite string-rewriting system that is normalized and weight-reducing. For w ∈ Σ^{∗}, let w_{0} ∈ IRR(R) denote the unique irreducible descendant of w with respect to leftmost reductions. Then a shrinking DTPDA M(R) = (Q, Σ, Γ, δ, q_{0}, ⊥, {q_{f}}) can be constructed such that, for each w ∈ Σ^{∗}, ⊥q_{0}w⊥ ⊢_{M(R)}^{∗} ⊥φ_{2}(w_{0})q_{f}. Here Σ_{2} ⊆ Γ \ Σ is an alphabet in 1-to-1 correspondence to Σ, and φ_{2} : Σ^{∗} → Σ_{2}^{∗} is the corresponding isomorphism.

Let R be a string-rewriting system on Σ, and let w ∈ IRR(R). Then ∇_{R}^{L}(w) := {u ∈ Σ^{∗} | u _{L} →_{R}^{∗} w} is the set of all leftmost ancestors of w.

For S ⊆ IRR(R), ∇_{R}^{L}(S) := ⋃_{w∈S} ∇_{R}^{L}(w).

Theorem 14. Let R be a normalized and weight-reducing string-rewriting system on Σ, and let S ⊆ IRR(R) be a regular language. Then the set ∇_{R}^{L}(S) is accepted by some sDTPDA.

Proof. Since S ⊆ IRR(R) is a regular language, there exists a DFA B on Σ_{2} such that L(B) = {(φ_{2}(w))^{R} | w ∈ S}. Here Σ_{2} is a new alphabet in 1-to-1 correspondence to Σ, φ_{2} : Σ^{∗} → Σ_{2}^{∗} is the corresponding isomorphism, and u^{R} denotes the reversal of u.

From Theorem 13 we get an sDTPDA M(R) := (Q, Σ, Γ, δ, q_{0}, ⊥, {q_{f}}) such that, for each w ∈ Σ^{∗}, ⊥q_{0}w⊥ ⊢_{M(R)}^{∗} ⊥φ_{2}(w_{0})q_{f}, where w_{0} ∈ IRR(R) is the unique irreducible string satisfying w _{L}→_{R}^{∗} w_{0}.

Now the DFA B and the sDTPDA M(R) are combined as follows. Given w ∈ Σ^{∗} as input, the combined DTPDA M first simulates M(R). However, when the string φ_{2}(w_{0}) has been computed, then, instead of erasing the bottom marker from the second pushdown store, M simulates the DFA B using its first pushdown store as input tape. Hence, M accepts the set ∇_{R}^{L}(S), and it is easily seen that the weight-function f of M(R) can be extended such that M is shrinking with respect to f. ⊓ ⊔

Actually, Theorem 14 can be extended to all languages S ⊆ IRR(R) that are accepted by shrinking DTPDAs.

If R is a finite weight-reducing string-rewriting system that is normalized and confluent, then [w]_{R} = ∇_{R}^{L}(w) for each string w ∈ IRR(R). Thus, Theorem 14 implies that in this situation, [S]_{R} := ⋃_{w∈S}[w]_{R} is accepted by some shrinking

DTPDA for each regular set S contained in IRR(R). Based on this observation we can now prove the intended converse of Theorem 11.

Theorem 15. Each generalized Church-Rosser language is accepted by some shrinking DTPDA.

Proof. Let S ⊆ Σ^{∗} be a GCRL. Then there are some alphabet Γ ⊃ Σ, a finite, weight-reducing, confluent string-rewriting system R on Γ, strings t_{1}, t_{2} ∈ (Γ \ Σ)^{∗} ∩ IRR(R) and a letter Y ∈ (Γ \ Σ) ∩ IRR(R) such that, for all w ∈ Σ^{∗}, t_{1}wt_{2} →_{R}^{∗} Y if and only if w ∈ S. Without loss of generality we can assume that the system R is normalized. Hence, by Theorem 14 there is an sDTPDA M_{1} that accepts the language ∇_{R}^{L}(Y) = [Y]_{R}. This sDTPDA M_{1} is now transformed into a shrinking DTPDA M_{2} that accepts the language S. M_{2} executes the following three steps.

(i) Before reading any input M_{2} writes φ_{2}(t_{1}) onto its first pushdown store. By assigning a sufficiently large weight to the initial state symbol, this step can be made weight-reducing.

(ii) Then M_{2} simulates the DTPDA M_{1}, that is, it computes a left-most reduction with respect to R. M_{2} continues with this simulation until it encounters the bottom marker ⊥ on its second pushdown store.

(iii) When the bottom marker ⊥ is encountered on the second pushdown store, then M_{2} pushes the string t_{2} onto the second pushdown store. Thereafter, it continues with the simulation of M_{1}. Since this intermediate step occurs only once, it can be made weight-reducing by introducing a second set of states in 1-to-1 correspondence to the states of M_{1}.

Thus, M_{2} accepts on input w ∈ Σ^{∗} if and only if t_{1}wt_{2} _{L}→_{R}^{∗} Y if and only if w ∈ S. Since M_{2} is an sDTPDA, this proves our result. ⊓ ⊔

Combining Theorem 11 and Theorem 15 we obtain the following characterization.

Corollary 16. A language is accepted by some sDTPDA if and only if it is a GCRL.

5 Separation Results

As is well-known GCSL is a proper subclass of CSL, since, for example, the Gladkij language {wc|w^{R}c|w | w ∈ {a, b}^{∗}} belongs to CSL\GCSL [Gla64, Boo69]. On the other hand, CFL is a proper subclass of GCSL, since already CRL contains the non-context-free language {a^{2^{n}} | n ≥ 0} [MNO88], while it is easily seen that each CFL is generated by some quasi-growing grammar. Finally, DCFL is properly contained in CFL as well as in CRL [MNO88]. Thus, the situation can be depicted as follows, where arrows indicate set inclusions, while dashed arrows indicate proper inclusions:

In addition, we know that CRL is not contained in CFL. In [MNO88] it has been conjectured that CFL is not contained in CRL, either. Here we will finally settle this conjecture in the affirmative. In fact, we will prove that CFL is not even contained in GCRL, which then implies that GCRL is strictly contained in GCSL. Thus, the shrinking TPDA is strictly more powerful than its deterministic variant.

Recall that an auxiliary pushdown automaton (auxPDA) with space bound s is a non-deterministic Turing machine M with a read-only input tape, a pushdown tape, and an auxiliary work tape which is initialized to have exactly s(n) squares, limited by end markers, if M is started on an input of length n. It is a one-way auxiliary pushdown automaton (OW-auxPDA) with space bound s, if it is limited to a one-way input tape. The closure of the class CFL of context-free languages under log-space reductions is denoted by LOGCFL, and OW-LOGCFL denotes the closure of the class CFL under one-way log-space reductions. It is known that LOGCFL coincides with the class of languages that are accepted by auxPDAs with logarithmic space bound and polynomial time bound [Sud78], and OW-LOGCFL coincides with the class of languages that are accepted by OW-auxPDAs with logarithmic space bound and polynomial time bound [Lau88].

For more details about auxPDAs see [HU79], for OW-auxPDAs see [Bra77, Chy77], and for one-way reductions see [HIM78].

Dahlhaus and Warmuth [DW86] have shown that the class GCSL is contained in LOGCFL. Using their technique actually the following stronger result can be obtained. Theorem 17. Each growing context-sensitive language is accepted by some OWauxPDA with logarithmic space bound and polynomial time bound, that is, GCSL is contained in OW-LOGCFL.

Based on this theorem we now derive the announced result. Let L_{0} denote the language L_{0} := {ww | w ∈ {a, b}^{∗}}. Then L_{0} is not context-free, while its complement L_{0}^{c} := {a, b}^{∗} \ L_{0} is a context-free language. However, it is known that L_{0} does not belong to OW-LOGCFL [Chy76, Lau88], and hence, by Theorem 17 L_{0} is not a growing context-sensitive language. Since the class GCRL is closed under complementation, this implies that L_{0}^{c} is not a generalized Church-Rosser language. Thus, we have the following consequences. Corollary 18. (a) The language classes GCRL and CFL are incomparable.

(b) The language classes CRL and CFL are incomparable.

(c) GCRL is a proper subclass of GCSL.

6 Conclusion

We have seen that each GCSL is accepted by some OW-auxPDA with logarithmic space bound and polynomial time bound. Surprisingly the generalized Church-Rosser languages, that is, the deterministic variants of the GCSL, are not accepted by the deterministic version of the OW-auxPDA, as witnessed by the language {w#w_{1}#w_{2}#i | w, w_{1}, w_{2} ∈ {0, 1}^{∗}, i ∈ {1, 2}, w = w_{i}^{R}}. However, a lot of open questions remain unanswered at this time.

First of all the generalized Church-Rosser languages are obtained from the Church-Rosser languages by admitting string-rewriting systems in the definition that are less severely restricted. Hence, CRL is contained in GCRL, but we don’t know yet whether this inclusion is a proper one. In [MNO88] it was not only conjectured that CFL ⊄ CRL, but in fact it was conjectured more specifically that the linear language L := {ww^{R} | w ∈ {a, b}^{∗}} is not a Church-Rosser language. Actually, we expect that L is not even a generalized Church-Rosser language, but we have no proof for this yet.

Also it has not yet been determined under which operations and mappings the classes GCRL and CRL are closed. It is easily seen that the class GCRL is closed under complement, reversal and intersection with regular sets. On the other hand, GCRL is neither closed under union nor under intersection. Nor is GCRL closed under alphabetic morphisms. Concerning the class CRL even less is known. It is closed under reversal, and under left and right quotient with a single string [MNO88], but for example, it is not even known whether it is closed under complement. If CRL is closed under inverse homomorphisms, then the classes CRL and GCRL coincide.

Finally, the classes CRL and GCRL should be compared to the various subclasses of the class CSL that Jančar, Mráz and Plátek define based on their machine model of a forgetting automaton [JMP93].

References

[BL92] G. Buntrock and K. Loryś. On growing context-sensitive languages. In Proc. of 19th ICALP, LNCS, 623:77–88, Springer, 1992.

[Boo69] R. V. Book. Grammars with Time Functions. PhD Diss., Harvard University, Cambridge, MA, 1969.

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

[Boo82] R. V. Book. Confluent and other types of Thue systems. Journal of the ACM, 29:171–182, 1982.

[BO93] R. V. Book and F. Otto. String-Rewriting Systems. Springer, 1993.

[Bra77] F.J. Brandenburg. On one-way auxiliary pushdown automata. In Proc. of 3rd GI-Conference on Theoretical Computer Science, LNCS, 48:132–144, Springer, 1977.

[Bun93] G. Buntrock. Growing context-sensitive languages and automata. Preprint, Nr. 69. Institut für Informatik, Universität Würzburg, November 1993.

[Chy76] M. Chytil. Analysis of the non-context-free component of formal languages. In Proc. of 5th MFCS, LNCS, 45:230–236, Springer, 1976.

[Chy77] M. Chytil. Comparison of the active visiting and the crossing complexities. In Proc. of 6th MFCS, LNCS, 53:272–281, Springer, 1977.

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

[GH68] S. Ginsburg and M. A. Harrison. One-way nondeterministic real-time liststorage languages. Journal of the ACM, 15:428–447, 1968.

[Gla64] A. W. Gladkij. On the complexity of derivations for context-sensitive grammars. Algebri i Logika Sem., 3:29–44, 1964. In Russian.

[HIM78] J. Hartmanis, N. Immerman, and S. R. Mahaney. One-way log-tape reductions. In Proc. of 19th FOCS, 1978, 65–71.

[HU79] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[JMP93] P. Janc̆ar, F. Mráz, and M. Plátek. A taxonomy of forgetting automata. In Proc. of 18th MFCS, LNCS, 711:527–536, Springer, 1993.

[Knu68] D. E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2:127–145, 1968.

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

[MNO88] R. McNaughton, P. Narendran, and F. Otto. Church-Rosser Thue systems and formal languages. Journal of the ACM, 35(2):324–344, 1988.

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

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

[Wal70] D. A. Walters. Deterministic context-sensitive languages: Part II. Information and Control, 17:41–61, 1970.

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

This article was processed using the LaTEX macro package with LLNCS style