umu.sePublications
Change search
ReferencesLink to record
Permanent link

Direct link
Deterministic Stack Transducers
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Institut fur Informatik, Universität Giessen.
2016 (English)In: Implementation and Application of Automata - 21st International Conference, {CIAA} 2016, Seoul, South Korea, July 19-22, 2016, Proceedings / [ed] Yo-Sub Han and Kai Salomaa, 2016Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2016.
Series
, Lecture Notes in Computer Science, 9705
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:umu:diva-125169ISBN: 978-3-319-40945-0OAI: oai:DiVA.org:umu-125169DiVA: diva2:959312
Conference
21st International Conference on Implementation and Application of Automata (CIAA 2016)
Available from: 2016-09-07 Created: 2016-09-07 Last updated: 2016-09-07

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Bensch, Suna
By organisation
Department of Computing Science
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link