Journal Article

Deterministic Deep Pushdown Transducer and its Parallel Version

Nidhi Kalra and Ajay Kumar

in The Computer Journal

Published on behalf of British Computer Society

Volume 61, issue 1, pages 63-73
Published in print January 2018 | ISSN: 0010-4620
Published online April 2017 | e-ISSN: 1460-2067 | DOI: http://dx.doi.org/10.1093/comjnl/bxx036
Deterministic Deep Pushdown Transducer and its Parallel Version

Show Summary Details

Preview

Abstract

Deep pushdown transducers (DPDT) are deterministic with respect to depth, but they lack strict determinism. The aim 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.

Keywords: deep pushdown transducer; parallel deep pushdown transducer; deterministic deep pushdown transducer; parallel deterministic deep pushdown transducer

Journal Article.  3590 words.  Illustrated.

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.