Information Technology Reference
In-Depth Information
A Polynomial-Time Algorithm for Checking
the Equivalence of Deterministic Restricted
One-Counter Transducers Which Accept
by Final State
Mitsuo Wakatsuki, Etsuji Tomita, and Tetsuro Nishino
Abstract.
This paper is concerned with a subclass of deterministic pushdown trans-
ducers, called deterministic restricted one-counter transducers (droct's), and studies
the equivalence problem for droct's which accept by final state. In the previous
study, we presented a polynomial-time algorithm for checking the equivalence of
real-time droct's. By extending the technique, we present a polynomial-time algo-
rithm for checking the equivalence of non-real-time droct's.
Keywords:
formal language theory, equivalence problem, deterministic pushdown
transducer,
deterministic
restricted
one-counter
transducer,
polynomial-time
algorithm.
1
Introduction
One of the most interesting questions in formal language theory is the equivalence
problem for deterministic pushdown automata (dpda's) and the corresponding de-
terministic context-free grammars. Although Senizergues [3] has proved that the
equivalence problem for any pair of dpda's is decidable, his algorithm is very com-
plicated and is hard to be implemented. A checking the equivalence for some dpda's
can play an important role in the learning process for these dpda's [4]. From a
Search WWH ::
Custom Search