A Polynomial-Time Algorithm for Checking the Equivalence of Deterministic Restricted One-Counter Transducers Which Accept by Final State

This paper is concerned with a subclass of deterministic pushdown transducers, 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 algorithm for checking the equivalence of non-real-time droct’s.