{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T04:18:18Z","timestamp":1749010698741,"version":"3.41.0"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319409450"},{"type":"electronic","value":"9783319409467"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40946-7_3","type":"book-chapter","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T11:52:20Z","timestamp":1467719540000},"page":"27-38","source":"Crossref","is-referenced-by-count":2,"title":["Deterministic Stack Transducers"],"prefix":"10.1007","author":[{"given":"Suna","family":"Bensch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johanna","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,6]]},"reference":[{"key":"3_CR1","unstructured":"Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, vol.\u00a0I: Parsing. Prentice-Hall, Upper Saddle River (1972)"},{"key":"3_CR2","unstructured":"Bojanczyk, M.: Transducers with origin information. In: Invited Talk at the 3rd International Workshop on Trends in Tree Automata and Tree Transducers, The Queen Mary University of London (2015)"},{"key":"3_CR3","unstructured":"Braune, F., Seemann, N., Quernheim, D., Maletti, A.: Shallow local multi-bottom-up tree transducers in statistical machine translation. In: Association for Computational Linguistics (ACL 2013), vol. 1, pp. 811\u2013821. The Association for Computer Linguistics (2013)"},{"key":"3_CR4","first-page":"47","volume":"82","author":"F Drewes","year":"2008","unstructured":"Drewes, F., van der Merwe, B.: Path languages of random permitting context tree grammars are regular. Fundam. Inform. 82, 47\u201360 (2008)","journal-title":"Fundam. Inform."},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/321371.321385","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: Stack automata and compiling. J. ACM 14, 172\u2013201 (1967)","journal-title":"J. ACM"},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1145\/321386.321403","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14, 389\u2013418 (1967)","journal-title":"J. ACM"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/S0019-9958(67)90513-X","volume":"11","author":"TN Hibbard","year":"1967","unstructured":"Hibbard, T.N.: A generalization of context-free determinism. Inform. Control 11, 196\u2013238 (1967)","journal-title":"Inform. Control"},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0019-9958(68)90722-5","volume":"13","author":"JE Hopcroft","year":"1968","unstructured":"Hopcroft, J.E., Ullman, J.D.: Sets accepted by one-way stack automata are context sensitive. Inform. Control 13, 114\u2013133 (1968)","journal-title":"Inform. Control"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Hori, C., Ohtake, K., Misu, T., Kashioka, H., Nakamura, S.: Weighted finite state transducer based statistical dialog management. In: Automatic Speech Recognition and Understanding (ASRU 2009), pp. 490\u2013495. IEEE (2009)","DOI":"10.1109\/ASRU.2009.5373350"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-3-319-19225-3_13","volume-title":"Descriptional Complexity of Formal Systems","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M., Wendlandt, M.: On simulation cost of unary limited automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 153\u2013164. Springer, Heidelberg (2015)"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-3-319-23111-2_8","volume-title":"Machines, Computations, and Universality (MCU 2015)","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M., Wendlandt, M.: Reversible limited automata. In: Durand-Lose, J., Nagy, B. (eds.) MCU 2015. LNCS, vol. 9288, pp. 113\u2013128. Springer, Switzerland (2015)"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/978-3-540-49127-9_28","volume-title":"Handbook on Speech Processing and Speech Communication, Part E: Speech Recognition","author":"M Mohri","year":"2008","unstructured":"Mohri, M., Pereira, F.C.N., Riley, M.: Speech recognition with weighted finite-state transducers. In: Benesty, J., Sondhi, M.M., Huang, Y. (eds.) Handbook on Speech Processing and Speech Communication, Part E: Speech Recognition, pp. 559\u2013584. Springer, Heidelberg (2008)"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Petrov, S.: Towards Universal Syntactic and Semantic Processing of Natural Language. Invited talk at SLTC 2016, Uppsala University (2014)","DOI":"10.3115\/v1\/W14-4208"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1142\/S0129054114400140","volume":"25","author":"G Pighizzini","year":"2014","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and regular languages. Int. J. Found. Comput. Sci. 25, 897\u2013916 (2014)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"157","DOI":"10.3233\/FI-2015-1148","volume":"136","author":"G Pighizzini","year":"2015","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and context-free languages. Fundamenta Inform. 136, 157\u2013176 (2015)","journal-title":"Fundamenta Inform."},{"key":"3_CR16","volume-title":"Computational Complexity","author":"K Wagner","year":"1986","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Reidel, Dordrecht (1986)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40946-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T23:56:07Z","timestamp":1748994967000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40946-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319409450","9783319409467"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40946-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}