umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Deterministic Stack Transducers
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
2017 (Engelska)Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, nr 5, s. 583-601Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
World Scientific Publishing Co. Pte. Ltd. , 2017. Vol. 28, nr 5, s. 583-601
Nyckelord [en]
Stack transducers, automata theory, computational capacity
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:umu:diva-143669DOI: 10.1142/S0129054117400081ISI: 000418091500010OAI: oai:DiVA.org:umu-143669DiVA, id: diva2:1171035
Konferens
21st International Conference on Implementation and Application of Automata (CIAA), JUL 19-22, 2016, Yonsei Univ, Seoul, SOUTH KOREA
Tillgänglig från: 2018-01-05 Skapad: 2018-01-05 Senast uppdaterad: 2018-06-09Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Bensch, SunaBjörklund, Johanna

Sök vidare i DiVA

Av författaren/redaktören
Bensch, SunaBjörklund, Johanna
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
International Journal of Foundations of Computer Science
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 399 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf