392
S. Akshay et al.
each push, pop of each stack to distinguish the ith push, jth pop and so on of
each stack. There are two holes of stack 1 (red stack) denoted by the red patches,
and one hole of stack 2 (blue stack) denoted by the blue patch. The subsequence
↓
1
1 ↓
2
1 ws 2 of the first hole is not a maximal factor, since it can be extended by
↓
3
1 ws 3 in the run σ, extending the hole. Consider the position in σ marked with
↓
1
2 . At this position, there is an open hole of the red stack (the first red patch),
and there is an open hole of the blue stack (the blue patch). Likewise, at the
position ↑
5
1 , there are 2 open holes of the red stack (2 red patches) and one open
hole of the blue stack 2 (the blue patch). The hole bound of σ is 3. The green
patch consisting of ↑
3
1 , ↑
2
1 and ws 5 is a pop-hole of stack 1. Likewise, the pops
↑
2
2 , ↑
5
1 , ↑
1
2 are all pop-holes (of length 1) of stacks 2,1,2 respectively.
Definition 2. (Hole Bounded Reachability Problem) Given a MPDA
and K ∈ N, the K-hole bounded reachability problem is the following: Does there
exist a K-hole bounded accepting run of the MPDA?
Proposition 1. The tree-width of K-hole bounded MPDA behaviors is at most
(2K + 3).
With this, from [22][5][6], decidability and complexity follow. Thus,
Corollary 1. The K-hole bounded reachability problem for MPDA is decidable
in O(|M|
2K+3 ) where, M is the size of the underlying MPDA.
Next, we turn to the expressiveness of this class with respect to the classical
underapproximations of MPDA: first, the hole bounded class strictly subsumes
scope bounded which already subsumes context bounded and round bounded
classes. Also hole bounded MPDA and phase bounded MPDA are orthogonal.
Proposition 2. Consider a MPDA M . For any K, let L K denote a set of sequences accepted by M which have number of rounds or number of contexts or
scope bounded by K. Then there exists K
≤ K such that L K is K
hole bounded.
Moreover, there exist languages which are K hole bounded for some constant K,
which are not K
round or context or scope bounded for any K
. Finally, there
exists a language which is accepted by phase bounded MPDA but not accepted by
hole bounded MPDA and vice versa.
Proof. We first recall that if a language L is K-round, or K-context bounded,
then it is also K
-scope bounded for some K
≤ K [20,19]. Hence, we only show
that scope bounded systems are subsumed by hole bounded systems.
Let L be a K-scope bounded language, and let M be a MPDA accepting
L. Consider a run ρ of w ∈ L in M . Assume that at any point i in the run ρ,
# i (holes) = k
, and towards a contradiction, let, k
> K. Consider the leftmost
open hole in ρ which has a pending push ↓ p whose pop ↑ p is to the right of
i. Since k
> K is the number of open holes at i, there are at least k
> K
context changes in between ↓ p and ↑ p . This contradicts the K-scope bounded
assumption, and hence k
≤ K.
To show the strict containment, consider the visibly pushdown language [7] given
by L
bh = {a
n b
n (a
p1 c
p1+1 b
p
1 d
p
1 +1
· · · a
pn c
pn+1 b
p
n d
p
n +1 ) | n, p 1 , p
1 , . . . , p n , p
n ∈
S. Akshay et al.
each push, pop of each stack to distinguish the ith push, jth pop and so on of
each stack. There are two holes of stack 1 (red stack) denoted by the red patches,
and one hole of stack 2 (blue stack) denoted by the blue patch. The subsequence
↓
1
1 ↓
2
1 ws 2 of the first hole is not a maximal factor, since it can be extended by
↓
3
1 ws 3 in the run σ, extending the hole. Consider the position in σ marked with
↓
1
2 . At this position, there is an open hole of the red stack (the first red patch),
and there is an open hole of the blue stack (the blue patch). Likewise, at the
position ↑
5
1 , there are 2 open holes of the red stack (2 red patches) and one open
hole of the blue stack 2 (the blue patch). The hole bound of σ is 3. The green
patch consisting of ↑
3
1 , ↑
2
1 and ws 5 is a pop-hole of stack 1. Likewise, the pops
↑
2
2 , ↑
5
1 , ↑
1
2 are all pop-holes (of length 1) of stacks 2,1,2 respectively.
Definition 2. (Hole Bounded Reachability Problem) Given a MPDA
and K ∈ N, the K-hole bounded reachability problem is the following: Does there
exist a K-hole bounded accepting run of the MPDA?
Proposition 1. The tree-width of K-hole bounded MPDA behaviors is at most
(2K + 3).
With this, from [22][5][6], decidability and complexity follow. Thus,
Corollary 1. The K-hole bounded reachability problem for MPDA is decidable
in O(|M|
2K+3 ) where, M is the size of the underlying MPDA.
Next, we turn to the expressiveness of this class with respect to the classical
underapproximations of MPDA: first, the hole bounded class strictly subsumes
scope bounded which already subsumes context bounded and round bounded
classes. Also hole bounded MPDA and phase bounded MPDA are orthogonal.
Proposition 2. Consider a MPDA M . For any K, let L K denote a set of sequences accepted by M which have number of rounds or number of contexts or
scope bounded by K. Then there exists K
≤ K such that L K is K
hole bounded.
Moreover, there exist languages which are K hole bounded for some constant K,
which are not K
round or context or scope bounded for any K
. Finally, there
exists a language which is accepted by phase bounded MPDA but not accepted by
hole bounded MPDA and vice versa.
Proof. We first recall that if a language L is K-round, or K-context bounded,
then it is also K
-scope bounded for some K
≤ K [20,19]. Hence, we only show
that scope bounded systems are subsumed by hole bounded systems.
Let L be a K-scope bounded language, and let M be a MPDA accepting
L. Consider a run ρ of w ∈ L in M . Assume that at any point i in the run ρ,
# i (holes) = k
, and towards a contradiction, let, k
> K. Consider the leftmost
open hole in ρ which has a pending push ↓ p whose pop ↑ p is to the right of
i. Since k
> K is the number of open holes at i, there are at least k
> K
context changes in between ↓ p and ↑ p . This contradicts the K-scope bounded
assumption, and hence k
≤ K.
To show the strict containment, consider the visibly pushdown language [7] given
by L
bh = {a
n b
n (a
p1 c
p1+1 b
p
1 d
p
1 +1
· · · a
pn c
pn+1 b
p
n d
p
n +1 ) | n, p 1 , p
1 , . . . , p n , p
n ∈