Information Technology Reference
In-Depth Information
practical point of view, it is desirable to have a polynomial-time algorithm for check-
ing the equivalence.
A
deterministic one-counter automaton
(
doca
) is a dpda having only one stack
symbol, with the exception of a bottom-of-stack marker. A
deterministic restricted
one-counter automaton
(
droca
) is a dpda which has only one stack symbol. The
class of languages accepted by droca's is a proper subclass of that of languages
accepted by doca's. Moreover, the class of languages accepted by droca's which
accept by final state properly contains the class of regular languages. Valiant has
shown that the equivalence problem for doca's is decidable in single exponential
time [8] [9] and the inclusion problem for doca's is undecidable [8]. On the other
hand, Higuchi et al. have presented polynomial-time algorithms for checking the
inclusion (also the equivalence) of droca's which accept by empty stack [1] and of
real-time droca's which accept by final state [2].
A deterministic pushdown transducer (dpdt) is a dpda provided with outputs. The
equivalence problem for dpdt's is essentially more difficult than that for dpda's. In
this paper, we are concerned with a subclass of dpdt's called
deterministic restricted
one-counter transducers
(
droct's
), which are droca's provided with outputs, and
study the equivalence problem for non-real-time droct's which accept by final state.
Since these droct's may have infinite sequences of
-moves, it is possible that their
stack heights increase infinitely without reading inputs. In the previous study, we
presented a polynomial-time algorithm for checking the equivalence of a pair of
real-time droct's (i.e. droct's without
ε
-moves) [10]. By extending the technique in
Ref. [10], we present a new direct branching algorithm for checking the equivalence
of non-real-time droct's (i.e. droct's with possible
ε
-moves). The worst-case time
complexity of our algorithm is polynomial in the description length of these droct's.
ε
2
Definitions and Notation
We assume that the reader is familiar with the basics of automata and formal lan-
guage theory. Our definitions and notation are almost as in Ref. [10].
Definition 1.
A
deterministic pushdown transducer
(
dpdt
for short) which accepts
by final state is denoted by
T
are the
finite sets of states, stack symbols, input symbols, output symbols, and transition-
output rules respectively,
q
0
(
∈
=(
Q
,
Γ
,
Σ
,
Δ
,
μ
,
q
0
,
Z
0
,
F
)
,where
Q
,
Γ
,
Σ
,
Δ
,
μ
Q
)
is the initial state,
Z
0
(
∈
Γ
)
is the initial stack
Γ
∗
,
Σ
∗
symbol, and
F
(
⊆
Q
)
is the set of final states. We denote an empty string in
Δ
∗
by
or
ε
.
z
−→
(
a
/
The set
μ
of
transition-output rules
is a set of rules of the form
(
p
,
A
)
q
,
θ
)
∈
Δ
∗
,
θ
∈
Γ
∗
, that satisfies the following
with
p
,
q
∈
Q
,
A
∈
Γ
,
a
∈
Σ
∪{
ε
}
,
z
conditions:
(i)
z
−→
(
a
/
If
(
p
,
A
)
q
,
θ
)
with
a
∈
Σ
∪{
ε
}
is in
μ
,then
μ
contains no rule of the form
z
−→
(
a
/
,
z
=
(
p
,
A
)
r
,
γ
)
for any
(
r
,
γ
)
=(
q
,
θ
)
z
.
z
−→
(
z
−→
(
ε
/
a
/
(ii)
If
(
p
,
A
)
q
,
θ
)
is in
μ
,then
μ
contains no rule of the form
(
p
,
A
)
r
,
γ
)
Search WWH ::
Custom Search