Automata theory is a corner stone of theoretical computer science. As such, it has applications in a wide variety of domains, from compilers and parsers to system verification and protocol specification. Automata and formal grammars are also central to natural language processing, where they are used in e.g. speech recognition and various kinds of textual analysis, increasingly in a cross-media context.

In a recent paper by Prof. Martin Kutrib together with Suna Bench and Johanna Björklund of the MICO NLP team, 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. 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 of different versions of these devices and show that also the strongest variant have nice mathematical properties.

The paper will be presented at 21st International Conference on Implementation and Application of Automata, July 19 -22, 2016, in Seoul, South Korea.

By Richardfabi – Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=49116