{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:20:40Z","timestamp":1780496440983,"version":"3.54.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2016,1,27]],"date-time":"2016-01-27T00:00:00Z","timestamp":1453852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,27]],"date-time":"2016-01-27T00:00:00Z","timestamp":1453852800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["FI 12-126689"],"award-info":[{"award-number":["FI 12-126689"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["RC 21413101"],"award-info":[{"award-number":["RC 21413101"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00236-015-0253-y","type":"journal-article","created":{"date-parts":[[2016,1,27]],"date-time":"2016-01-27T07:19:53Z","timestamp":1453879193000},"page":"509-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["On reversible Turing machines and their function universality"],"prefix":"10.1007","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0034-2874","authenticated-orcid":false,"given":"Holger Bock","family":"Axelsen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Gl\u00fcck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,1,27]]},"reference":[{"key":"253_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/3-540-36377-7_13","volume-title":"The Essence of Computation: Complexity, Analysis, Transformation","author":"S Abramov","year":"2002","unstructured":"Abramov, S., Gl\u00fcck, R.: Principles of inverse computation and the universal resolving algorithm. In: Mogensen, T.\u00c6., Schmidt, D.A., Sudborough, I.H. (eds.) The Essence of Computation: Complexity, Analysis, Transformation. Lecture Notes in Computer Science, vol. 2566, pp. 269\u2013295. Springer, Heidelberg (2002)"},{"key":"253_CR2","first-page":"142","volume-title":"Compiler Construction, CC 2011. Proceedings, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2011","unstructured":"Axelsen, H.B.: Clean translation of an imperative reversible programming language. In: Knoop, J. (ed.) Compiler Construction, CC 2011. Proceedings, Lecture Notes in Computer Science, vol. 6601, pp. 142\u2013161. Springer, Heidelberg (2011)"},{"key":"253_CR3","first-page":"1","volume-title":"Reversible Computation, RC 2011. Revised Papers, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2012","unstructured":"Axelsen, H.B.: Time complexity of tape reduction for reversible Turing machines. In: De Vos, A., Wille, R. (eds.) Reversible Computation, RC 2011. Revised Papers, Lecture Notes in Computer Science, vol. 7165, pp. 1\u201313. Springer, Heidelberg (2012)"},{"key":"253_CR4","first-page":"117","volume-title":"LATA 2011. Proceedings, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2011","unstructured":"Axelsen, H.B., Gl\u00fcck, R.: A simple and efficient universal reversible Turing machine. In: Dediu, A.H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. Proceedings, Lecture Notes in Computer Science, vol. 6638, pp. 117\u2013128. Springer, Heidelberg (2011)"},{"key":"253_CR5","first-page":"42","volume-title":"FOSSACS 2011. Proceedings, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2011","unstructured":"Axelsen, H.B., Gl\u00fcck, R.: What do reversible programs compute? In: Hoffman, M. (ed.) FOSSACS 2011. Proceedings, Lecture Notes in Computer Science, vol. 6604, pp. 42\u201356. Springer, Heidelberg (2011)"},{"key":"253_CR6","first-page":"56","volume-title":"Computer Science\u2014Theory and Applications, CSR 2007. Proceedings, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2007","unstructured":"Axelsen, H.B., Gl\u00fcck, R., Yokoyama, T.: Reversible machine code and its abstract processor architecture. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) Computer Science\u2014Theory and Applications, CSR 2007. Proceedings, Lecture Notes in Computer Science, vol. 4649, pp. 56\u201369. Springer, Heidelberg (2007)"},{"key":"253_CR7","unstructured":"Axelsen, H.B., Holzer, M., Kutrib, M., Malcher, A.: Reversible shrinking two-pushdown automata. In: Dediu, A.H., Mart\u00edn-Vide, C., Truthe B. (eds.) LATA 2016. Proceedings, Lecture Notes in Computer Science. Springer, Heidelberg (2016). To appear"},{"key":"253_CR8","first-page":"29","volume-title":"Reversible Computation, RC 2015. Proceedings, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2015","unstructured":"Axelsen, H.B., Jakobi, S., Kutrib, M., Malcher, A.: A hierarchy of fast reversible Turing machines. In: Krivine, J., Stefani, J.B. (eds.) Reversible Computation, RC 2015. Proceedings, Lecture Notes in Computer Science, vol. 9138, pp. 29\u201344. Springer, Heidelberg (2015)"},{"key":"253_CR9","first-page":"407","volume-title":"APLAS 2015. Proceedings, Lecture Notes in Computer Science","author":"HB Axelsen","year":"2015","unstructured":"Axelsen, H.B., Yokoyama, T.: Programming techniques for reversible comparison sorts. In: Feng, X., Park, S. (eds.) APLAS 2015. Proceedings, Lecture Notes in Computer Science, vol. 9458, pp. 407\u2013426. Springer, Heidelberg (2015)"},{"issue":"6","key":"253_CR10","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"CH Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525\u2013532 (1973)","journal-title":"IBM J. Res. Dev."},{"key":"253_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1364\/ON.11.2.000011","volume":"11","author":"R Feynman","year":"1985","unstructured":"Feynman, R.: Quantum mechanical computers. Opt. News 11, 11\u201320 (1985)","journal-title":"Opt. News"},{"issue":"3","key":"253_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1232420.1232424","volume":"29","author":"JN Foster","year":"2007","unstructured":"Foster, J.N., Greenwald, M.B., Moore, J.T., Pierce, B.C., Schmitt, A.: Combinators for bi-directional tree transformations: a linguistic approach to the view update problem. ACM Trans. Programm. Lang. Syst. 29(3), 17 (2007)","journal-title":"ACM Trans. Programm. Lang. Syst."},{"key":"253_CR13","first-page":"246","volume-title":"APLAS 2003. Proceedings, Lecture Notes in Computer Science","author":"R Gl\u00fcck","year":"2003","unstructured":"Gl\u00fcck, R., Kawabe, M.: A program inverter for a functional language with equality and constructors. In: Ohori, A. (ed.) APLAS 2003. Proceedings, Lecture Notes in Computer Science, vol. 2895, pp. 246\u2013264. Springer, Heidelberg (2003)"},{"key":"253_CR14","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-540-24754-8_21","volume-title":"Functional and Logic Programming. Proceedings, Lecture Notes in Computer Science","author":"R Gl\u00fcck","year":"2004","unstructured":"Gl\u00fcck, R., Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing. In: Kameyama, Y., Stuckey, P.J. (eds.) Functional and Logic Programming. Proceedings, Lecture Notes in Computer Science, vol. 2998, pp. 291\u2013306. Springer, Heidelberg (2004)"},{"key":"253_CR15","doi-asserted-by":"crossref","unstructured":"Gl\u00fcck, R., Kawada, Y., Hashimoto, T.: Transforming interpreters into inverse interpreters by partial evaluation. In: Proceedings of the Partial Evaluation and Semantics-Based Program Manipulation, PEPM 2003, pp. 10\u201319. ACM Press (2003)","DOI":"10.1145\/966049.777391"},{"key":"253_CR16","first-page":"137","volume-title":"Partial Evaluation. Proceedings, Lecture Notes in Computer Science","author":"R Gl\u00fcck","year":"1996","unstructured":"Gl\u00fcck, R., S\u00f8rensen, M.: A roadmap to metacomputation by supercompilation. In: Danvy, O., Gl\u00fcck, R., Thiemann, P. (eds.) Partial Evaluation. Proceedings, Lecture Notes in Computer Science, vol. 1110, pp. 137\u2013160. Springer, Heidelberg (1996)"},{"key":"253_CR17","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2003.001.0001","volume-title":"Computability and Complexity: From a Programming Language Perspective. Foundations of Computing","author":"ND Jones","year":"1997","unstructured":"Jones, N.D.: Computability and Complexity: From a Programming Language Perspective. Foundations of Computing. MIT Press, Cambridge (1997)"},{"key":"253_CR18","first-page":"368","volume-title":"LATA 2010. Proceedings, Lecture Notes in Computer Science","author":"M Kutrib","year":"2010","unstructured":"Kutrib, M., Malcher, A.: Reversible pushdown automata. In: Dediu, A.H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. Proceedings, Lecture Notes in Computer Science, vol. 6031, pp. 368\u2013379. Springer, Heidelberg (2010)"},{"key":"253_CR19","first-page":"14","volume-title":"Reversible Computation, RC 2012. Revised Papers, Lecture Notes in Computer Science","author":"M Kutrib","year":"2012","unstructured":"Kutrib, M., Malcher, A.: One-way reversible multi-head finite automata. In: Gl\u00fcck, R., Yokoyama, T. (eds.) Reversible Computation, RC 2012. Revised Papers, Lecture Notes in Computer Science, vol. 7581, pp. 14\u201328. Springer, Heidelberg (2012)"},{"issue":"3","key":"253_CR20","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(3), 183\u2013191 (1961)","journal-title":"IBM J. Res. Dev."},{"key":"253_CR21","first-page":"2597","volume":"257","author":"Y Lecerf","year":"1963","unstructured":"Lecerf, Y.: Machines de Turing r\u00e9versibles. R\u00e9cursive insolubilit\u00e9 en $$n\\in {N}$$ de l\u2019\u00e9quation $$u=\\theta ^n u$$, o\u00f9 $$\\theta $$ est un \u201cisomorphisme de codes\u201d. Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie des Sciences 257, 2597\u20132600 (1963)","journal-title":"Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie des Sciences"},{"key":"253_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"1993","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York (1993)"},{"key":"253_CR23","first-page":"177","volume-title":"Automata Studies","author":"J McCarthy","year":"1956","unstructured":"McCarthy, J.: The inversion of functions defined by Turing machines. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 177\u2013181. Princeton University Press, Princeton (1956)"},{"issue":"1","key":"253_CR24","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2008.01.041","volume":"395","author":"K Morita","year":"2008","unstructured":"Morita, K.: Reversible computing and cellular automata\u2014A survey. Theo. Comp. Sci. 395(1), 101\u2013131 (2008)","journal-title":"Theo. Comp. Sci."},{"issue":"3","key":"253_CR25","first-page":"223","volume":"72","author":"K Morita","year":"1989","unstructured":"Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. Trans. IEICE E 72(3), 223\u2013228 (1989)","journal-title":"Trans. IEICE E"},{"key":"253_CR26","first-page":"90","volume-title":"Machines, Computations and Universality, MCU 2007. Proceedings, Lecture Notes in Computer Science","author":"K Morita","year":"2007","unstructured":"Morita, K., Yamaguchi, Y.: A universal reversible Turing machine. In: Durand-Lose, J., Margenstern, M. (eds.) Machines, Computations and Universality, MCU 2007. Proceedings, Lecture Notes in Computer Science, vol. 4664, pp. 90\u201398. Springer, Heidelberg (2007)"},{"key":"253_CR27","first-page":"2","volume-title":"APLAS 2004. Proceedings, Lecture Notes in Computer Science","author":"SC Mu","year":"2004","unstructured":"Mu, S.C., Hu, Z., Takeichi, M.: An algebraic approach to bi-directional updating. In: Chin, W.N. (ed.) APLAS 2004. Proceedings, Lecture Notes in Computer Science, vol. 3302, pp. 2\u201320. Springer, Heidelberg (2004)"},{"issue":"1","key":"253_CR28","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.jlap.2009.02.006","volume":"79","author":"M Schellekens","year":"2010","unstructured":"Schellekens, M.: MOQA; unlocking the potential of compositional static average-case analysis. J. Log. Algebr. Program. 79(1), 61\u201383 (2010)","journal-title":"J. Log. Algebr. Program."},{"key":"253_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2710-6","volume-title":"What Computing Is All About","author":"JLA van de Snepscheut","year":"1993","unstructured":"van de Snepscheut, J.L.A.: What Computing Is All About. Springer, New York (1993)"},{"issue":"2","key":"253_CR30","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1142\/S0129626409000171","volume":"19","author":"MK Thomsen","year":"2009","unstructured":"Thomsen, M.K., Axelsen, H.B.: Parallelization of reversible ripple-carry adders. Parallel Process. Lett. 19(2), 205\u2013222 (2009)","journal-title":"Parallel Process. Lett."},{"key":"253_CR31","first-page":"30","volume-title":"Reversible Computation, RC 2011. Revised Papers, Lecture Notes in Computer Science","author":"MK Thomsen","year":"2012","unstructured":"Thomsen, M.K., Axelsen, H.B., Gl\u00fcck, R.: A reversible processor architecture and its reversible logic design. In: De Vos, A., Wille, R. (eds.) Reversible Computation, RC 2011. Revised Papers, Lecture Notes in Computer Science, vol. 7165, pp. 30\u201342. Springer, Heidelberg (2012)"},{"issue":"38","key":"253_CR32","first-page":"2002","volume":"42","author":"MK Thomsen","year":"2010","unstructured":"Thomsen, M.K., Gl\u00fcck, R., Axelsen, H.B.: Reversible arithmetic logic unit for quantum arithmetic. J. Phys. A Math. Theo. 42(38), 2002 (2010)","journal-title":"J. Phys. A Math. Theo."},{"key":"253_CR33","first-page":"632","volume-title":"ICALP 1980. Proceedings, Lecture Notes in Computer Science","author":"T Toffoli","year":"1980","unstructured":"Toffoli, T.: Reversible computing. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. Proceedings, Lecture Notes in Computer Science, vol. 85, pp. 632\u2013644. Springer, New York (1980)"},{"issue":"4","key":"253_CR34","first-page":"339","volume":"1","author":"Y Van Rentergem","year":"2005","unstructured":"Van Rentergem, Y., De Vos, A.: Optimal design of a reversible full adder. Int. J. Unconv. Comput. 1(4), 339\u2013355 (2005)","journal-title":"Int. J. Unconv. Comput."},{"key":"253_CR35","doi-asserted-by":"crossref","unstructured":"Yokoyama, T., Axelsen, H.B., Gl\u00fcck, R.: Principles of a reversible programming language. In: Computing Frontiers, CF 2008. Proceedings, pp. 43\u201354. ACM Press (2008)","DOI":"10.1145\/1366230.1366239"},{"key":"253_CR36","unstructured":"Yokoyama, T., Axelsen, H.B., Gl\u00fcck, R.: Fundamentals of reversible flowchart languages. Theo. Comp. Sci. 611, 87\u2013115 (2016)"},{"key":"253_CR37","doi-asserted-by":"crossref","unstructured":"Yokoyama, T., Gl\u00fcck, R.: A reversible programming language and its invertible self-interpreter. In: Partial Evaluation and Program Manipulation, PEPM 2007. Proceedings, pp. 144\u2013153. ACM Press (2007)","DOI":"10.1145\/1244381.1244404"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0253-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-015-0253-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0253-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0253-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T10:35:27Z","timestamp":1589625327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-015-0253-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,27]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["253"],"URL":"https:\/\/doi.org\/10.1007\/s00236-015-0253-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,27]]},"assertion":[{"value":"25 September 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 December 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}