A Polynomial-Time Algorithm for Checking the Equivalence for Real-Time Deterministic Restricted One-Counter Transducers Which Accept by Final State
Mitsuo Wakatsuki, Etsuji Tomita, Tetsuro Nishino · 2013
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 real-time droct's which accept by final state. After providing some properties of these droct's, we present a polynomial-time algorithm for checking the equivalence for these droct's.