{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:23:51Z","timestamp":1743121431517,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319948119"},{"type":"electronic","value":"9783319948126"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94812-6_3","type":"book-chapter","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T22:12:26Z","timestamp":1530223946000},"page":"28-40","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Boosting Pushdown and Queue Machines by Preprocessing"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Malcher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Wendlandt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"3_CR1","volume-title":"The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing. Prentice-Hall Inc., Englewood Cliffs (1972)"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (ed.) Symposium on Theory of Computing (STOC 2004), pp. 202\u2013211. ACM (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-319-40578-0_6","volume-title":"Reversible Computation","author":"HB Axelsen","year":"2016","unstructured":"Axelsen, H.B., Kutrib, M., Malcher, A., Wendlandt, M.: Boosting reversible pushdown machines by preprocessing. In: Devitt, S., Lanese, I. (eds.) RC 2016. LNCS, vol. 9720, pp. 89\u2013104. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40578-0_6"},{"key":"3_CR4","unstructured":"Axelsen, H.B., Kutrib, M., Malcher, A., Wendlandt, M.: Boosting reversible pushdown and queue machines by preprocessing (2018, Submitted to a journal)"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"von Braunm\u00fchl, B., Verbeek, R.: Input-driven languages are recognized in $$\\log n$$ space. In: Karpinski, M., van Leeuwen, J. (eds.) Topics in the Theory of Computation, Mathematics Studies, vol. 102, pp. 1\u201319. North-Holland, Amsterdam (1985)","DOI":"10.1016\/S0304-0208(08)73072-X"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0304-3975(91)90053-5","volume":"85","author":"A Cherubini","year":"1991","unstructured":"Cherubini, A., Citrini, C., Crespi-Reghizzi, S., Mandrioli, D.: QRT FIFO automata, breadth-first grammars and their relations. Theor. Comput. Sci. 85, 171\u2013203 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1137\/0215049","volume":"15","author":"C Citrini","year":"1986","unstructured":"Citrini, C., Crespi-Reghizzi, S., Mandrioli, D.: On deterministic multi-pass analysis. SIAM J. Comput. 15(3), 668\u2013693 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2003.10.007","volume":"313","author":"N Friburger","year":"2004","unstructured":"Friburger, N., Maurel, D.: Finite-state transducer cascades to extract named entities in texts. Theor. Comput. Sci. 313(1), 93\u2013104 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR9","volume-title":"Introduction to Formal Language Theory","author":"MA Harrison","year":"1978","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978)"},{"issue":"6","key":"3_CR10","doi-asserted-by":"publisher","first-page":"1814","DOI":"10.1016\/j.jcss.2011.12.004","volume":"78","author":"M Kutrib","year":"2012","unstructured":"Kutrib, M., Malcher, A.: Reversible pushdown automata. J. Comput. Syst. Sci. 78(6), 1814\u20131827 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.tcs.2015.01.012","volume":"578","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M., Malcher, A., Mereghetti, C., Palano, B., Wendlandt, M.: Deterministic input-driven queue automata: finite turns, decidability, and closure properties. Theor. Comput. Sci. 578, 58\u201371 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-319-30000-9_12","volume-title":"Language and Automata Theory and Applications","author":"M Kutrib","year":"2016","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Input-driven queue automata with internal transductions. In: Dediu, A.-H., Janou\u0161ek, J., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 156\u2013167. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-30000-9_12"},{"issue":"3\u20134","key":"3_CR13","doi-asserted-by":"publisher","first-page":"341","DOI":"10.3233\/FI-2016-1438","volume":"148","author":"M Kutrib","year":"2016","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Reversible queue automata. Fundam. Inform. 148(3\u20134), 341\u2013368 (2016)","journal-title":"Fundam. Inform."},{"issue":"1\u20132","key":"3_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.3233\/FI-2017-1576","volume":"155","author":"M Kutrib","year":"2017","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Tinput-driven pushdown, counter, and stack automata. Fundam. Inform. 155(1\u20132), 59\u201388 (2017)","journal-title":"Fundam. Inform."},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1147\/rd.53.0183","volume":"5","author":"R Landauer","year":"1961","unstructured":"Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183\u2013191 (1961)","journal-title":"IBM J. Res. Dev."},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","author":"K Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: de Bakker, J., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 422\u2013435. Springer, Heidelberg (1980). https:\/\/doi.org\/10.1007\/3-540-10003-2_89"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/2636805.2636821","volume":"45","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A., Salomaa, K.: Complexity of input-driven pushdown automata. SIGACT News 45(2), 47\u201367 (2014)","journal-title":"SIGACT News"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94812-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:45:38Z","timestamp":1709826338000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94812-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319948119","9783319948126"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94812-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Charlottetown, PE","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.smcs.upei.ca\/ciaa2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}