Conference paper

Publication year: 2017

Pages: 583-601

Journal: International Journal of Foundations of Computer Science

Volume number: 28

Issue number: 5

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054117400081

Conference: 21st International Conference on Implementation and Application of Automata (CIAA)

Publisher: World Scientific Publishing

Abstract: 
We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural-language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures. We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular.

Harvard Citation style: Bensch, S., Bjorklund, J. and Kutrib, M. (2017) Deterministic Stack Transducers, International Journal of Foundations of Computer Science, 28(5), pp. 583-601. https://doi.org/10.1142/S0129054117400081

APA Citation style: Bensch, S., Bjorklund, J., & Kutrib, M. (2017). Deterministic Stack Transducers. International Journal of Foundations of Computer Science. 28(5), 583-601. https://doi.org/10.1142/S0129054117400081