Deterministic Deep Pushdown Transducer and its Parallel Version

摘要

Deep pushdown transducers (DPDT) are deterministic with respect to depth, but they lack strict determinism. The of this paper is to address the open problem of determinism in DPDT, as discussed in [1], by proposing a deterministic DPDT (DDPDT). Furthermore, we also explore a parallel variant of a DDPDT. The proposed deterministic models are strictly deterministic as well as deterministic with respect to depth. We support this discussion of these transducers with numerical examples. Furthermore, relationships among deterministic transducers, non-strict deterministic transducers and their parallel variants will be discussed.