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.
Institut fur Informatik, Universität Giessen.
2016 (Engelska)Ingår i: Implementation and Application of Automata / [ed] Yo-Sub Han and Kai Salomaa, Springer, 2016, s. 27-38Konferensbidrag, Publicerat paper (Refereegranskat)
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
Springer, 2016. s. 27-38
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9705
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:umu:diva-125169DOI: 10.1007/978-3-319-40946-7_3ISI: 000389401500003ISBN: 978-3-319-40945-0 (tryckt)ISBN: 978-3-319-40946-7 (tryckt)OAI: oai:DiVA.org:umu-125169DiVA, id: diva2:959312
Konferens
21st International Conference on Implementation and Application of Automata (CIAA 2016), Seoul, South Korea, July 19-22, 2016
Tillgänglig från: 2016-09-07 Skapad: 2016-09-07 Senast uppdaterad: 2018-06-07Bibliografiskt 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
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 447 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