umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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 / [ed] Yo-Sub Han and Kai Salomaa, Springer, 2016, 27-38 p.Conference paper, Published 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
Springer, 2016. 27-38 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9705
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:umu:diva-125169DOI: 10.1007/978-3-319-40946-7_3ISI: 000389401500003ISBN: 978-3-319-40945-0 (print)ISBN: 978-3-319-40946-7 (print)OAI: oai:DiVA.org:umu-125169DiVA: diva2:959312
Conference
21st International Conference on Implementation and Application of Automata (CIAA 2016), Seoul, South Korea, July 19-22, 2016
Available from: 2016-09-07 Created: 2016-09-07 Last updated: 2017-01-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Bensch, SunaBjörklund, Johanna
By organisation
Department of Computing Science
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 87 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf