{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T11:35:31Z","timestamp":1774956931034,"version":"3.50.1"},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1142\/s0129054117400081","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T08:31:43Z","timestamp":1513326703000},"page":"583-601","source":"Crossref","is-referenced-by-count":12,"title":["Deterministic Stack Transducers"],"prefix":"10.1142","volume":"28","author":[{"given":"Suna","family":"Bensch","sequence":"first","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, 90187 Ume\u00e5, Sweden"}]},{"given":"Johanna","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, 90187 Ume\u00e5, Sweden"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2017,12,15]]},"reference":[{"key":"S0129054117400081BIB001","volume-title":"The Theory of Parsing, Translation, and Compiling","author":"Aho A. V.","year":"1972"},{"key":"S0129054117400081BIB004","first-page":"47","volume":"82","author":"Drewes F.","year":"2008","journal-title":"Fund. Inform."},{"key":"S0129054117400081BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"S0129054117400081BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321385"},{"key":"S0129054117400081BIB007","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321403"},{"key":"S0129054117400081BIB008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1967-0209086-1"},{"key":"S0129054117400081BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90513-X"},{"key":"S0129054117400081BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90722-5"},{"key":"S0129054117400081BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114400140"},{"key":"S0129054117400081BIB017","doi-asserted-by":"crossref","first-page":"157","DOI":"10.3233\/FI-2015-1148","volume":"136","author":"Pighizzini G.","year":"2015","journal-title":"Fund. Inform."},{"key":"S0129054117400081BIB018","volume-title":"Computational Complexity","author":"Wagner K.","year":"1986"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117400081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,24]],"date-time":"2020-10-24T09:49:27Z","timestamp":1603532967000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117400081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":11,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,12,15]]},"published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1142\/S0129054117400081"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117400081","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}