Complexity Results on Balanced Context-Free
Languages
Akihiko Tozawa1 and Yasuhiko Minamide2
1

IBM Research,
Tokyo Research Laboratory, IBM Japan, ltd.
2
Department of Computer Science
University of Tsukuba

Abstract. Some decision problems related to balanced context-free languages are important for their application to the static analysis of programs generating XML strings. One such problem is the balancedness
problem which decides whether or not the language of a given contextfree grammar (CFG) over a paired alphabet is balanced. Another important problem is the validation problem which decides whether or not
the language of a CFG is contained by that of a regular hedge grammar(RHG). This paper gives two new results; (1) the balancedness problem is
in PTIME; and (2) the CFG-RHG containment problem is 2EXPTIMEcomplete.

1

Introduction

The study of balanced context-free languages or parenthesis context-free languages dates back to the 1960s and 1970s [McN67,Knu67,Tak75]. Recently balanced context-free languages attract new interests because of their application
to XML-related problems [BB02b,BB02a,KM06], e.g., the static analysis of programs generating XML strings. In the previous work [MT06], we give algorithms
to two such problems. This paper continues that study and gives answers to
problems previously left open.
Let A be a base alphabet. Then, we introduce a paired alphabet consistingof two sets Á and À:Á = { á | a ∈ A }À = { à | a ∈ A }where Á and À correspond to the set of start tags and the set of end tags,
respectively. We consider that á and à match. We write Σ for Á ∪ À. Then thefundamental notion on a string over a paired alphabet is whether it is balanced.
For example, áb́b̀ćc̀à and áàb́b̀ are balanced, but áb̀ and áb́b̀ are not. This notionof balanced strings corresponds to well-formed documents in XML. We call theset of all balanced strings B(Σ) the Dyck set over Σ [Ber79].
We consider context-free grammars over paired alphabets. The ﬁrst problem
to ask is the balancedness problem. Namely, whether or not the language of agiven context-free grammar (CFG) G is balanced, or whether or not L(G) ⊆B(Σ). To our knowledge, the best known algorithm for this problem requires
exponential time. However this is not optimal. We will prove that this problem
in actually in PTIME.
This PTIME algorithm consists of two steps. The ﬁrst step is to check thebalancedness of the language as a grammar of a single kind of parentheses. We
here use a ﬁxpoint algorithm based on the algorithms by Knuth [Knu67], andBerstel and Boasson [BB02b]. However, we give a ﬁner analysis of the number of
iterations needed to reach ﬁxpoint, which at ﬁrst glance seems to be exponential
to the size of the grammar, but in fact it is linear. The second step is to checkeach matched letters are of the same kind. Consider a CFG G with a singleton
language. Such a CFG is sometimes called a straight line program (SLP). Assume
that in this G, we have a production rule I → XY whose X and Y derive stringsφ ∈ Á∗ and ψ ∈ À∗ , respectively, of the same length. Now clearly, the singleton
language of G is balanced if φ is identical to the reverse of ψ by ignoring ´ and `signs. Plandowski has shown that the problem of deciding the equivalence of two
SLPs, and hence the balancedness of this L(G), is in PTIME [Pla94]. We latershow how to apply Plandowski’s algorithm to the problem for general CFGs.
The second problem is the validation problem. Our previous work discussed
the problem whether L(G) ⊆ L(G ) holds where G is a CFG and G is either
an (i) XML grammar or (ii) regular hedge grammar (RHG). In particular, theRHG deﬁnes an important language class corresponding to regular languages
over trees. Indeed, any regular hedge language can be deﬁned only from thefollowing two kinds of productions.
X → áY àZ

or X → .

This corresponds to non-deterministic tree automata (NTA) on binary trees.
The best known time complexity for the CFG-RHG containment is doubly exponential. This is actually optimal. In this paper, we prove that this problem is
2EXPTIME-hard.
A parenthesis grammar (PG) [McN67,Knu67] is a grammar with a single
kind of parentheses, e.g., [ and ], and with production rules restricted to thefollowing form.
X → [Y1 · · · Yk ]or X → aHere letters a can be considered as the abbreviation of áà. It is then easy to seethat the class of the PG is a subclass of the class of the RHG. We actually provethat the containment L(G) ⊆ L(G ) where G is PG is already 2EXPTIMEhard. The idea of the proof comes from the observation of the gap between
derivation trees and parse trees of balanced languages generated from CFGs.
Namely, a single node on a parse tree, i.e., matching parentheses, can be split
to two 2O(n) -distant nodes in the corresponding derivation tree.
The rest of the paper is organized as follows. Section 2 explains the algorithm for the balancedness problem. Section 3 proves 2EXPTIME-hardness of
the CFG-RHG containment problem. Section 4 summarizes the related work.

X.......

n

d(φ)

σ

c(φ)
(a) c(φ) and d(φ)c(φX)(b) derivation tree of φX
Fig. 1. Illustration of c(φ), d(φ) and φX

2PTIME Balancedness CheckWe develop an algorithm which decides in polynomial time whether or not thelanguage of a context-free grammar is balanced. The algorithm has two steps.
In the ﬁrst step, we only check shapes of strings. The language of a grammar
is shape-balanced iﬀ it is balanced by treating it as if using a single pair ofparentheses, e.g., áb̀ is not balanced, but shape-balanced. In this step, we also
pick up a string with the deepest valley in the set of strings produced from eachnonterminal. The second step is the check of color-balancedness, i.e., we neversee corresponding á and b̀ such that a = b.
In this section, we assume a grammar G = (Σ, V, R, I) such that all production rules are in the form X → α or X → αβ where α, β ∈ Σ  V . We canconvert arbitrary CFGs into this form in linear size3 . We also assume that G
is reduced. That is, every nonterminal is accessible from the start symbol andevery nonterminal produces at least one terminal string. By a notation C[], wemean a string containing a hole, which is ﬁlled with a string φ as C[φ].
2.1

Checking Balancedness of Shapes

The shape of a string is intuitively understood by reading this string from left
to right as a line graph. Each letter à corresponds to a descending slope of thegraph, and each á to a climbing slope of the same unit, respectively. Now we
obtain the shape of a string by– Keeping the levels of both ends of this line graph.
3

More precisely, we obtain G such that L(G) = L(G ) \ {} from G . Removing  does
not change the balancedness.

– Erase all valleys other than the one deepest in the graph.
Formally, we say a string φ is shape-balanced if repeatedly removing all matchingáb̀ from φ gives an empty string. Any string φ ∈ Σ ∗ is reduced to the following
form with this reduction.
ài · · · à1 b́1 · · · b́j
We identify the shape of φ by c(φ) and d(φ) deﬁned as c(φ) = i and d(φ) = i − j.
Here c(φ) is a nonnegative integer denoting the depth of the deepest valley
measured from the left end, and d(φ) is a possibly-negative integer denoting
the level of the right end measured from the left end (cf. Fig. 1(a)). A string φis shape-balanced iﬀ c(φ) = d(φ) = 0. The language L(G) of a grammar G isshape-balanced if all strings in the language are shape-balanced.
If a grammar has a shape-balanced language, each language corresponding∗
to its nonterminal X has constant d(φ), i.e., d(φ) = d(ψ) if X ⇒ φ, ψ. Further∗more, for each nonterminal X, there is a bound m such that X ⇒ φ implies∗c(φ) ≤ m. To see this, consider the derivation I ⇒ C[X]. This C[] must be in
the form ψ0 á1 ψ1 · · · ái ψi []ζj b̀j · · · b̀1 ζ0 with ψ0 , . . . , ψi , ζ0 , . . . , ζj shape-balanced.
∗
Since c(C[φ]) = d(C[φ]) = 0 for any X ⇒ φ, we have c(φ) ≤ i and d(φ) = i − j.
The bound of c(φ) implies the existence of, not necessarily unique, element∗
φX such that X ⇒ φX with maximum depth c(φX ) (= m). Here is the main
proposition about this φX .
Proposition 1. Assume G = (Σ, V, R, I) such that L(G) is shape-balanced.
For each X ∈ V , we have φX with maximum c(φX ), such that the height of thederivation tree is bounded by 2n + 1 where n = |V |.
Note that L(G) is shape-balanced iﬀ c(φI ) = d(φI ) = 0. This proposition bounds
the number of iterations to ﬁnd out φI , which is linear to the size of the grammar.
To prove this proposition, we need analysis on primary paths of derivation trees.
∗
See Fig. 1(b). This ﬁgure explains how given a derivation tree for X ⇒ φ, we
compute the depth of each valley in φ. Assume a path t0 , t1 , . . . , tk (= t) in thederivation tree where t0 is the root, and t is a leaf labeled either as á or à. We
would like to compute the depth c(t) of the valley found around this occurrenceof á or à. Intuitively, this value is computed from the sum of all d(ψ) where ψ isa substring corresponding to each branch appearing in the left of the path to t.
In this path, each non-leaf node ti is labeled by a nonterminal X ∈ V andassociated with a rule X → α or X → αβ ∈ R. If ti+1 is the ﬁrst successor ofti labeled by α, the derivation by X → α or X → αβ does not contribute todeepening the valley around t. On the other hand, if ti+1 is the second successor∗
labeled by β, c(t) is increased by d(ψ) where α ⇒ ψ is a sub-derivation for theﬁrst successor of ti . If the leaf node t is labeled by á, the valley exists on theleft of this occurrence of á. On the other hand, if it is à, the valley exists on theright, so that we increase c(t) by 1. Now the primary path of φ is a path to aleaf t in the derivation tree with maximum c(t). Then clearly this c(t) is equalto c(φ).

Now assume that the grammar has a shaped-balanced language. Then the
problem of ﬁnding out φX maximizing c(φX ) becomes the problem of ﬁndingout a primary path, in a certain derivation tree for X, to the leaf t maximizingc(t).
This problem can be considered as a graph problem. We can draw a graphwhose vertices correspond to V  Σ, and whose edge from X to γ corresponds to
X → γ or X → αβ ∈ R such that either γ = α or β. Now we assign the weightcorresponding to the increase in the depth c(t) to each edge of this graph. The
grammar has a shaped-balanced language, so that we can determine constantd(φX ) for each nonterminal X. Let d(φá ) = −1 and d(φà ) = 1.
– For each edge from X to α where α ∈ V  Á,• if this edge corresponds to X → α or X → αβ, we give the weight 0,• if this edge corresponds to X → βα, we give the weight d(φβ ).
– For each edge from X to à,• if this edge corresponds to X → à or X → àβ, we give the weight 1,• if this edge corresponds to X → βà, we give the weight d(φβ ) + 1.
For example, consider the following grammar with the shape-balanced language.
I → Z0 Z1

Z0 → áb́

Z1 → Z1 I

Z1 → b̀à
∗In this grammar, we always have d(φ) = −2 if Z0 ⇒ φ, so that the edge from I
to Z1 is given weight −2.
0

b́ o

−1

Z0 o
0


á

0

Io

2

−2



@ Z1

b̀

2

/ à

1

The problem of ﬁnding out a primary path with maximum weight ﬁrst corresponds to the detection of positive cycles in the graph. If there is no such cycle,
the problem reduces to the longest (maximum-weight) path problem.
Indeed, if the grammar has a shaped-balanced language, the graph constructed as such has no positive cycles. If there is such a cycle, clearly wefail to ﬁnd any primary path with maximum weight, contradicting the shapebalancedness. On the other hand, if there is no such cycle, then for any pathcontaining the same vertex twice, we can always ﬁnd another path with at least
the same weight, and without such duplicated occurrence of vertices. Now thisproves that we can always ﬁnd a maximum-weight path of length at most n + 1.
Fig. 1(b) illustrates how we construct φX . The length of the primary path inφX can be made at most n+1. We can use arbitrary derivation trees for subtrees
not related to the primary path, whose height can be made at most n + 1. To
sum up, the height of the derivation of φX can be made at most 2n + 1, proving
Proposition 1.

2.2

Straight Line Programs for φX

If only concerning the shape-balancedness, it is enough to compute the shapeof this φX , i.e., c(φX ) and d(φX ). This is rather easy. However for the colorbalancedness, we need to compute φX themselves. Unfortunately, in the worst
case, φX are not of polynomial length, so that we cannot obtain a PTIME
algorithm if they are explicitly represented as strings. We here consider thecompressed string representation using sharing graphs.
Definition 1. (Straight Line Program) A straight line program (SLP) is anacyclic CFG without alternatives in production rules.
In other words, an SLP is a CFG generating a singleton set. We give an algorithm
to ﬁnd each φX as an SLP in Fig. 2. This algorithm combines the ﬁxpoint
algorithm of shape-balancedness check with Bellman-Ford’s algorithm for the
longest path problem where the graph does not contain positive cycles [Law76].
This algorithm needs to be repeated 2n + 1 times. After S2n+1 is computed,
we ﬁrst check S2n+1 (X) = S2n (X) for all X ∈ V . If so, this means that thealgorithm reaches the ﬁxpoint, so that it could ﬁnd φX with maximum depth foreach X. Otherwise, the algorithm could not ﬁnd φX with the height of derivation
2n + 1, so that the shape-balancedness has failed from Proposition 1. The ﬁrst
and second component of S2n (X) denote c(φX ) and d(φX ), respectively, so that
we then check that S2n (I) = (0, 0, ).
After the shape-balancedness check has passed, we construct φX for eachnonterminal X of the grammar. The third component of S2n (X) corresponds toprimary paths in the SLP for φX . We introduce a set of nonterminals V = {X |X ∈ V } and deﬁne the set of rules P in the form X → θ where θ = α, αβ or αβ.
P = {X → θ | S2n (X) = ( , , X → θ), X ∈ V }This P corresponds to the longest paths trees of Bellman-Ford algorithm computing a collection of longest paths for any source-target pair in the graph. For
example, the following trees show the solution of the longest path problem inthe previous section, where target vertices correspond to terminals.
b́

Z0 o

0

I

Z1

2

/ à

0


á

b̀

This means that we use the same set of rules P to compute any φX . The following
P corresponds to the above solution where á = á and à = à.
I → Z 0 Z1

Z 0 → áb́

Z 1 → b̀àFinally, we construct a set of rules U . This is by induction on the depth k ofthe derivation. Let U0 = {}, and at k +1-th step, choose and add exactly one rule

Input CFG (Σ, V, R, I).
Output A mapping Sk ∈ (Σ  V ) → (N×N×({X → θ | θ = α, αβ, αβ}{•}){⊥}).
1 We first initialize S0 (X) for X ∈ V and Sk (σ) for σ ∈ Σ as follows.
S0 (X) = ⊥, Sk (á) = (0, −1, •), Sk (à) = (1, 1, •)2 We iteratively compute Sk+1 (X) for X ∈ V as follows.
– For each of (i) X → α or (ii) X → αβ, such that Sk (α) and Sk (β) (if (ii)) arenot ⊥. Assume that Sk (α), Sk (β) and Sk (X) (if not ⊥) are as follows.
Sk (α) = (c1 , d1 , ), Sk (β) = (c2 , d2 , ), Sk (X) = (c0 , d0 , )In case (ii) with Sk (X) = ⊥, we first confirm that d0 = d1 + d2 . If this fails,
the shape-balancedness has failed. We then compute Sk+1 (X) as follows. Let
d3 = d1 + d2 , c3 = d1 + c2 , and σ = σ.
8(c1 , d1 , X → α) ((i), c1 > c0 if Sk (X) = ⊥)>><(c1 , d3 , X → αβ) ((ii), c1 ≥ c3 , and c1 > c0 if Sk (X) = ⊥)Sk+1 (X) =>(c, d , X → αβ) ((ii), c1 < c3 , and c3 > c0 if Sk (X) = ⊥)>: 3 3(otherwise)
Sk (X)
Fig. 2. Combined algorithm for computing primary paths

Y → α or Y → αβ in R to Uk+1 such that Y ∈/ dom(Uk ), and α, β ∈ dom(Uk ).
Here dom(U ) = Σ  {Y ∈ V | Y → ∈ U }. We let U = Un . By construction,dom(U ) = Σ  V , for each Y ∈ V we have exactly one rule in U , and U induces
no cycles.
The following SLP only has the size linear to the original grammar G.
Algorithm 1 We obtain the SLP for φX as (Σ, V  V , U  P, X).
2.3

Checking Color-Balancedness

The remaining step of the balancedness check is to conﬁrm that each pair ofcoupled parentheses in strings is of the same color, i.e., of the same base letter in
A. If so we call such strings color-balanced, or partially-balanced since they canbe deﬁned as substrings of balanced strings. A string is balanced iﬀ it is bothshape-balanced and color-balanced.
A color-balanced string φ is factorized as φ−i ài φi−1 · · · à1 φ0 b́1 φ1 · · · b́j φj suchthat φ−i , . . . , φj are balanced. Even an arbitrary string can be similarly factorized by allowing φ−i , . . . , φj to be shape-balanced. According to this factorization, we deﬁneρ(φ) = ài · · · à1 b́1 · · · b́j
Next we deﬁne an orderingon À∗ Á∗ as the minimal one satisfyingφψ

φàáψ

for φ ∈ À∗ and ψ ∈ Á∗ . We again extend this to a quasi-ordering φψ ⇔ρ(φ) ρ(ψ). Note that φ ψ implies c(φ) ≤ c(ψ). Now, the remaining part of
the algorithm is fairly simple.
Algorithm 2 (Balancedness Check) Assume that we already computed φX withmaximum c(φX ) for each nonterminal of the given grammar G = (Σ, V, R, I).
We let φσ = σ. For each X ∈ V , we check the following:– φX is color-balanced.
– φX φα , if X → α ∈ R.
– φα φβ is color-balanced and φX

φα φβ , if X → αβ ∈ R.

It is easy to see that a grammar with a balanced language satisﬁes these conditions. This follows from the fact that under the balancedness, any φX withmaximum c(φX ) bounds all strings generated from X also according to . The
other direction is shown by the following proposition; the success of Algorithm 2
implies the color-balancedness of the language of the grammar which, together
with the shape-balanced check, proves the balancedness of the language.
∗

Proposition 2. If the check succeeds, X ⇒ φ implies (i) φ is color-balanced,and (ii) φX φ.
The proof is by induction on the length of the derivation of φ. The base case isabout terminal symbols and easy. For inductive step, assume that the proposition
holds for strings obtained by derivation whose height is not greater than k. Now∗
consider the derivation X ⇒ φ with its height k + 1. If X → αβ is used,∗∗
we have φ1 φ2 = φ such that α ⇒ φ1 and β ⇒ φ2 . Note that it is safe toreplace a substring ψ of a color-balanced string with another color-balanced
string ψ  compatible to ψ. Formally, if (a) ψ  and C[ψ] are color-balanced, and(b) ψ ψ  , we have (c) C[ψ  ] color-balanced and (d) C[ψ] C[ψ  ]. Now we provethe case as follows. By assumption, (a) φα φβ , φ1 and φ2 are color-balanced, we
φ1 and φβ
φ2 . Hence (c) φ is color-balanced, and (d)also have (b) φα
φX φα φβ φ1 φβ φ1 φ2 = φ. The case X → α is easy.
2.4

SLP and CS Equivalence

Finally, we need to conﬁrm that for strings given as SLPs, both the colorbalancedness and the check of φ
ψ are decidable in PTIME. Fortunately,
as noted in the introduction, we can use Plandowski’s algorithm deciding theequivalence of two SLPs in PTIME.
First we give some deﬁnitions. Let φo be strings created from φ just by taking
letters in Á and removing ´ sign. Let φc be strings created from φ similarly forÀ but in addition, by reversing the obtained string. For example, (àb̀ć)o = c and(àb̀ć)c = ba. We use φ[j, k] to denote a substring of φ starting from its j-th letterand ending before the k-th letter.

Input SLP (Σ, V, R, I)
Output CS (A, V c  V o , R , I c or I o )1 For a rule X → αβ ∈ R, we let o1 = c(φα ) − d(φα ), c2 = c(φβ ), and m = min(c2 , o1 ).
X o → αo [0, o1 − m]β o
X c → β c [0, c2 − m]αc
2 For a rule X → α, we just define
X c → αc , X o → αo2 Finally for letters we defineác = ào = , áo = àc = a,Fig. 3. Translation of SLP for φX into CS for ρ(φX )Proposition 3. Let cj = |ρ(φj )c |, oj = |ρ(φj )o |, and m = min(o1 , c2 ).
(i) We have φ1 φ2 color-balanced iﬀ φ1 and φ2 are color-balanced, andρ(φ1 )o [o1 − m, o1 ] = ρ(φ2 )c [c2 − m, c2 ](ii) We have φ1

φ2 iﬀ s = c2 − c1 = o2 − o1 ≥ 0, andρ(φ1 )c = ρ(φ2 )c [s, c2 ]ρ(φ1 )o = ρ(φ2 )o [s, o2 ]ρ(φ2 )o [0, s] = ρ(φ2 )c [0, s](iii) A composition system (CS) is an SLP which allows occurrences of nonterminals in the form X[j, k] in the rhs of productions. Given an SLP generating∗∗
φ, the translation in Fig. 3 gives CS such that I c ⇒ ρ(φ)c and I o ⇒ ρ(φ)o .
It is known that the equivalence problem of two CSs also has a PTIME
algorithm, since a CS can always be converted back into a polynomial-size
SLP [Hag00,Sch06]. We use this algorithm with the property (ii) to determine
φ2 . We also use it with the property (i) to create a proof tree showφ1
ing that each φX is (or is not) color-balanced by checking, for each production
Y → αβ needed in constructing φX , that two CS, i.e., those using start symbols
αo [o1 − m, o1 ] and β c [c2 − m, c2 ], are equivalent.
Now the following theorem is immediate from Proposition 2 and 3.
Theorem 1. The balancedness problem is in PTIME.

3

2EXPTIME-Completeness of CFG-RHG Containment

We show that the CFG-RHG containment problem is 2EXPTIME-complete. In
our previous work, we developed a decision algorithm for the problem which has

[□ … [□
[ a0
[ a1

a0 ]
a1 ]

[ ak-1[ ak[ ak+1ak-1 ]ak ]ak+1][ a2k-1

a2k-1]

[ a2k

a2k ]

k

□

a0

a0

ak

a1 ak+1
−→

ak

a2k

□] … □]

Fig. 4. A derivation tree and parse tree

doubly exponential time complexity [MT06]. Here we prove that this algorithm
is actually optimal by showing that the problem is 2EXPTIME-hard.
As noted in the introduction, we actually show the 2EXPTIME-hardness of
the CFG-PG containment problem. The result for the CFG-RHG containmentis immediately obtained by regarding PGs as RHGs. For this, we distinguish asingle pair of parenthesis [ and ]. We use an abbreviation a = áà and use A todenote the set of strings in this form.
3.1

The Key Observation

Seidl [Sei90] showed that the containment between the languages of two nondeterministic tree automata (NTA) is EXPTIME-complete. In fact, NTA deﬁnes
the class of tree languages corresponding to languages of parse trees obtained
from string languages deﬁned by PG. If the problem is PG-PG or RHG-RHG
containment, or even if the lhs of the containment is a balanced grammar suchthat c(φX ) = d(φX ) = 0 for all X ∈ V , the complexity relaxes to EXPTIME. In
the case of NTA-containment, the size of the lhs is merely a polynomial factor.
On the other hand, in the CFG-PG containment problem, the primary factorof the complexity is CFG on lhs. We here explain the high 2EXPTIME complexity from the gap between a derivation tree and parse tree of each string in
the language of this CFG. Each node in a derivation tree corresponds to a nonterminal, while each node in a parse tree corresponds to matched parentheses.
In the case of balanced grammars, two trees are not so diﬀerent in the sense that

k

α0

α1

α1

k
αi
[◇ …[◇αi ◇...◇

αi

...

α0

k

αi ◇...◇

αi-1 αi2k...

αi aik+0◇... ◇

αi αi

...

αi+1

...

αi+1’ k□] …□]□] …□]α1−→αi ◇... ◇ αi aik+0◇... ◇duplicating αi
αi aik+0 ... aik+k-2◇
αi αi+1αi αi

αi αi+1’

branchFig. 5. Simulation of a branch in ATM

each matching parentheses also exist closely, i.e., as siblings, in a derivation tree.
This is generally not the case for a grammar just with a balanced language.
First note that for arbitrary k ∈ N and φ ∈ Σ ∗ , we can construct a CFG(SLP) Iφk of size O(log k) that accepts φk . For this, we deﬁne X0 → φ, Xi+1 →Xi Xi , and Iφk → Xi1 . . . Xin where i1 , .., in -th bits are set in the binary encodingof k. Now let 2 ∈ A and deﬁne a grammar G askk
X, X → I2]
and X → [aXa] for a ∈ A
I → I[2generating the following strings.
kk    
[2 · · · [2[a0 [a1 · · · 2] · · · 2] · · · a1 ]a0 ]See also a derivation tree for this grammar described as the left tree of Fig. 4.
In the ﬁgure, double-ended arrows between parentheses indicate matched parentheses. We can see that each matched parentheses exist in k-distant positions in
the derivation tree. Hence, a parse tree of the language of this grammar looks
like the right tree of Fig. 4.
Now the procedure that decides L(G) ⊆ L(Gpg ) can be considered as aprocedure which checks whether all parse trees above are contained in L(Gpg ) as
trees. This PG compares the sequence a0 · · · ak−1 with ak · · · a2k−1 , ak · · · a2k−1
with a2k · · · a3k−1 , and so on. The ﬁrst idea for the hardness proof is to use thisfact to simulate a Turing machine (TM) using k-space. Let αi = aik · · · a(i+1)k−1
be a conﬁguration of TM. It is possible to construct a PG to check if eachtransition from αi to αi+1 is a valid single computation step of the given TM.
Although this idea indeed works as we will later formally discuss, we need
one more trick to prove the 2EXPTIME-hardness. Note here that the size of G isO(log k). This means that the above TM can only solve EXPSPACE problems.
To obtain the 2EXPTIME-hardness, we consider alternating Turing machines(ATM). An ATM is a Turing machine with conjunctive transitions in the formq  q1 ∧ q2 4 . A computation of an ATM is thus a tree with branching degrees atmost 2, and each 2-degree branch corresponds to this ∧-transition. It is known
that the class of 2EXPTIME is identical to the problems solvable by ATM using
exponential space [CKS81].
The idea to simulate ATM is to add the following production rules to theprevious grammar.
k
X → I[3Y, Y → XX and Y → [aY a] for a ∈ A

A derivation tree of this grammar may look like the left tree of Fig. 5. We
simplify the ﬁgure by omitting most of [ and ], and we also group each length-ksequence of leaves aik , · · · , a(i+1)k−1 along the main branch as αi . Now, we atsome timing start to use Y instead of X in the main branch of the derivation, andthis branch by Y eventually ends with two branches of derivations by X. Now
the right tree of Fig. 5 explains how such derivation is parsed. In this ﬁgure, eachnode corresponding to the derivation by Y is illustrated as twice as wide as nodes
for X. This reﬂects d(φY ) = 2k and d(φX ) = k. This also means that the PG can
now simulate a machine with 2k-space here. We would like to use this machine
to duplicate the information of αi before the branch. Such a duplication can bedone by O(k)-computation steps, whose each step can be checked by constantsize PG. After successfully creating αi αi , we can simulate alternating transitions
, by checking two child branches independently.
αi to αi+1 , and αi to αi+1
Using this idea, we will prove the following theorem in the next section.
Theorem 2. The CFG-PG containment problem is 2EXPTIME-hard.
3.2

Proof of 2EXPTIME-Hardness

Let P be a 2EXPTIME problem and M be an ATM solving this problem using
exponential space. This ATM M is a tuple (Q, Γ, , q0 , 2, H) where– Q is a set of states,– Γ is a set of symbols,–  ⊆ (Γ × Q × {−1, 0, 1} × Γ × Q)  (Q × {q ∧ q  | q, q  ∈ Q}) is a transition
relation,– q0 is an initial state,– 2 ∈ Γ is a blank symbol, and– H is a set of accepting states.
4

In the literature, conjunctive transitions q  q1 ∧ q2 are often expressed by using∀-states, which correspond to branches in the computation tree, of possibly morethan degree 2. It is easy to see that such an ATM using many-degreed branches canbe easily converted into an equivalent ATM using at most 2-degree branches.

A conﬁguration of M is α = s0 · · · si−1 sqi si+1 · · · ∈ Γ ∗ (Γ × Q)Γ ω whereindicates that the current state is q and the head is at i-th position. The
computation of M starts from α0 = xq00 x1 · · · xn−1 2 · · · where x = x0 · · · xn−1
is an input. If |x| = n, the computation of M uses no more than k = 2p(n) spacefor some polynomial p. A computation history of M is a ﬁnite tree T = (T, α)associated with a function α ∈ T → Γ ∗ (Γ × Q)Γ ω . This T is of branchingdegrees at most 2, so that the set of nodes T is given as a ﬁnite downward-closed
subset of {1, 2}∗ under lexicographic ordering on {1, 2}∗ . For each node t ∈ T ,α(t) represents the conﬁguration at t. Each degree 2 branch in T corresponds
to alternating transitions q  q1 ∧ q2 . If x ∈ P , we can ﬁnd T whose all leaves
t satisfy sqi ∈ α(t) for some q ∈ H. Otherwise, any T has some leaves with
non-accepting states.
Given an input x = x0 · · · xn−1 , we can construct the following CFG G in
deterministic polynomial time and with its size polynomial to the input:
sqi

k−n
X
I → [#[xq00 · · · [xn−1 I[2
X → [aXa] for a ∈ Ak
X → [#I[3Yk
X → #]I2]
Y → [aY a] for a ∈ A
Y → XX

where we let k = 2p(n) , Q• = {•}  Q, A = {#}  Γ × Q• = {#}  Γ  Γ × Q,
A = {#}  (Γ × Q•  {3}) × {!}• . We add the symbol # to recognize boundaries of each conﬁguration.
We would like to create a PG Gpg or equivalently NTAs such that any parsetree in L(G) \ L(Gpg ) corresponds to an accepting computation history in thesense as explained in the last section. We model the parse tree as in Fig. 4 bya tree U = (U, λ) associated with a labeling function λ ∈ U → A × A. Any
φ ∈ L(G) can be parsed as such U . This U also has branching degrees at most
2. Any NTA running on U can be eﬃciently converted into an equivalent PG onφ.
First, we rule out ill-formed trees such that either # is not inserted appropriately, or 2-degree branches occur at inappropriate positions. For this, we use NTA
N1 which accepts any tree U with u ∈ U such that either (i) λ(u) = (#, s), (s, #)where s = #, or (ii) λ(u) = (#, #) and u is of branching degree 2.
Before simulating an alternation step of the ATM, we need to copy a conﬁgk
uration. By the production X → [#I[3Y , we prepare the copy and obtain the
conﬁguration below.
# s0 s1 · · · sqi · · · sk−1 # 3 3 · · ·3#At the ﬁrst step, we place two markers denoted by ! at the two positions after#, then repeatedly move two markers to the right and copy the contents.
# s0 s1 · · · sqi · · · sk−1 # 3 3 · · ·# s!0 s1 · · · sqi · · · sk−1 # 3! 3 · · ·3#
3#

# s!0 s1 · · · sqi · · · sk−1 # 3! 3
# s0 s!1 · · · sqi · · · sk−1 # s0 3!
..
.
# s0 s1 · · · sqi · · · s!k−1 # s0 s1# s0 s1 · · · sqi · · · sk−1 # s0 s1

···
···

3 #
3 #

···
···

3! #
sk−1 #

This process is checked by an NTA N2 , which checks each sequence of nodes
u0 , . . . , un , . . . , um ∈ U such that (i) each ui+1 is the successor of ui , (ii) λ(ui ) =(#, #) iﬀ i = 0, n, m, (iii) λ(ui ) = (3, ) or (3! , ) for some n < i < m. Notethat any tree in L(G) \ L(N1 ) contains such a sequence only when n = k + 1 andm = 2k +2. N2 accepts a tree which contains an incorrect copying sequence, e.g.,λ(ui ) = (s! , s), λ(uj ) = (3! , s ) and s = s for some i, j. This N2 also accepts atree if one of (i) λ(um−1 ) = (3! , ) and (ii) the node um is of branching degree
2, exclusively holds.
Finally, we construct an NTA N3 for checking the transitions of M . Thisis similar to N2 except that we check a sequence u0 , . . . un such that λ(u0 ) =λ(un ) = (#, #) without occurrence of ! and # on nodes u1 . . . un−1 . This N3
accepts U whenever it ﬁnds a sequence u0 , . . . , un such that u0 is of branchingdegree 1, but the sequence is either (i) not obeying  when un is also of branchingdegree 1, or (ii) not containing accepting state, i.e., no ui such that λ(ui ) =(sq , 2) for some q ∈ H, when un is a leaf. This N3 also accepts U whenever it
ﬁnds u0 ∈ U of branching degree 2, followed by two sequences u0 , u1 , . . . , un and
u0 , u1 , . . . , um , which does not have i and j such that (i) λ(ui ), λ(uj  ) are in theform (s, s) if i = i and j  = j, and (ii) λ(ui ) = (sq , sq1 ) and λ(uj ) = (sq , sq2 ) forsome alternating transition q  q1 ∧ q2 .
We obtain the parenthesis grammar Gpg from an NTA accepting the union ofL(N1 ), L(N2 ) and L(N3 ). The size of this Gpg is independent of x. Now for any
x, we construct G in deterministic polynomial time from x so that we have x ∈ P
iﬀ ¬L(G) ⊆ L(Gpg ). Hence the CFG-PG containment is 2EXPTIME-hard.

4

Related WorkIn the same paper as the SLP equivalence [Pla94], Plandowski has also shown
the existence of a polynomial-size test set for given CFG G. A test set T ⊆ L(G)is such that given two morphisms h, h ∈ Σ → M for a free group M , if h(φ) =h (φ) for all φ ∈ T then this holds for all φ ∈ L(G). He computed this T as a setof SLPs. Hence if we can eﬃciently decide whether or not h(φ) =  for all φ ∈ T ,by letting h (σ) =  (= unit of M ) for all σ ∈ Σ, we obtain the PTIME algorithm
to a problem similar to the balancedness problem which decides whether or noth(L(G)) = {}. One diﬀerence here is that aa−1 = a−1 a =  holds in a freegroup, while àá is irreducible in the balancedness problem. We are not sure if
we have another polynomial time algorithm for the balancedness problem in thisdirection.
Meyer and Stockmeyer showed that the equivalence problem for regularexpressions extended with squaring is EXPSPACE-hard and further investi-

gated the complexity of the problems for various variants of regular expressions [MS72,SM73]. For tree languages, Seidl showed that the equivalence of nondeterministic tree automata is EXPTIME-complete using an alternating Turing
Machine as our discussion [Sei90]. The proofs of these completeness results are
based on the hardness of the corresponding universality problems for languagesof the rhs of the containment. On the other hand, in our proof of 2EXPTIMEcompleteness of CFG-RHG containment, a CFG in the lhs of the containmentis essential.

References[BB02a] Jean Berstel and Luc Boasson. Balanced grammars and their languages. In
Formal and Natural Computing: Essays Dedicated to Grzegorz, volume 2300
of LNCS, pages 3–25, 2002.
[BB02b] Jean Berstel and Luc Boasson. Formal properties of XML grammars andlanguages. Acta Informatica, 38(9):649–671, 2002.
[Ber79] Jean Berstel. Transductions and Context-Free Languages. Teubner Studienbucher, 1979.
[CKS81] Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation.
J. ACM, 28(1):114–133, 1981.
[Hag00] Christian Hagenah. Gleichungen mit regulären Randbedingungen über freien
Gruppen. PhD thesis, Universität Stuttgart, Fakultät Informatik, 2000.
[KM06] Christian Kirkegaard and Anders Møller. Static analysis for Java Servlets
and JSP. In Proc. 13th International Static Analysis Symposium, SAS ’06,
volume 4134 of LNCS, August 2006.
[Knu67] Donald E. Knuth. A characterization of parenthesis languages. Information
and Control, 11(3):269–289, 1967.
[Law76] Eugene Lawler. Combinatorial Optimization: Networks and Matroids, chapter 3. 1976.
[McN67] Robert McNaughton. Parenthesis grammars. Journal of the Association for
Computing Machinery, 14(3):490–500, 1967.
[MS72] A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regularexpressions with squaring requires exponential space. In Conf. Rec. 13th IEEE
Symp. on Switching and Automata Theory, pages 125–129, 1972.
[MT06] Yasuhiko Minamide and Akihiko Tozawa. XML validation for context-freegrammars. In Proc. of The Fourth ASIAN Symposium on Programming Languages and Systems, volume 4279 of LNCS, pages 357–373, 2006.
[Pla94] Wojciech Plandowski. Testing equivalence of morphisms on context-free languages. In Algorithms – ESA ’94 (Utrecht), volume 855 of LNCS, pages
460–470. Springer, 1994.
[Sch06] Saul Schleimer. Polynomial-time word problems, 2006. http://front.math.
ucdavis.edu/math.GR/0608563.
[Sei90] Helmut Seidl. Deciding equivalence of finite tree automata. SIAM Journal on
Computing, 19(3):424–437, 1990.
[SM73] Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In STOC, pages 1–9, 1973.
[Tak75] Masako Takahashi. Generalizations of regular sets and their application to a
study of context-free languages. Information and Control, 21(1):1–36, 1975.