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.
2017 (English)In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, no 5, p. 583-601Article in journal (Refereed) Published
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
World Scientific Publishing Co. Pte. Ltd. , 2017. Vol. 28, no 5, p. 583-601
Keywords [en]
Stack transducers, automata theory, computational capacity
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:umu:diva-143669DOI: 10.1142/S0129054117400081ISI: 000418091500010OAI: oai:DiVA.org:umu-143669DiVA, id: diva2:1171035
Conference
21st International Conference on Implementation and Application of Automata (CIAA), JUL 19-22, 2016, Yonsei Univ, Seoul, SOUTH KOREA
Available from: 2018-01-05 Created: 2018-01-05 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Bensch, SunaBjörklund, Johanna

Search in DiVA

By author/editor
Bensch, SunaBjörklund, Johanna
By organisation
Department of Computing Science
In the same journal
International Journal of Foundations of Computer Science
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 381 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