{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T13:35:48Z","timestamp":1768743348327,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403125","type":"print"},{"value":"9783642403132","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_53","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T14:36:43Z","timestamp":1376663803000},"page":"595-606","source":"Crossref","is-referenced-by-count":6,"title":["Reversibility of Computations in Graph-Walking Automata"],"prefix":"10.1007","author":[{"given":"Michal","family":"Kunc","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"53_CR1","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/j.tcs.2005.07.002","volume":"347","author":"S. Abramsky","year":"2005","unstructured":"Abramsky, S.: A structural approach to reversible computation. Theoretical Computer Science\u00a0347(3), 441\u2013464 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"53_CR2","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"A.V. Aho","year":"1971","unstructured":"Aho, A.V., Ullman, J.D.: Translations on a context free grammar. Information and Control\u00a019(5), 439\u2013475 (1971)","journal-title":"Information and Control"},{"issue":"6","key":"53_CR3","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"C.H. Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development\u00a017(6), 525\u2013532 (1973)","journal-title":"IBM Journal of Research and Development"},{"key":"53_CR4","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0218053","volume":"81","author":"C.H. Bennett","year":"1989","unstructured":"Bennett, C.H.: Time\/space trade-offs for reversible computation. SIAM Journal on Computing\u00a081, 766\u2013776 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"53_CR5","doi-asserted-by":"crossref","unstructured":"Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: SWAT 1967, pp. 155\u2013160 (1967)","DOI":"10.1109\/FOCS.1967.6"},{"issue":"2-3","key":"53_CR6","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.tcs.2005.10.031","volume":"350","author":"M. Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata cannot be determinized. Theoretical Computer Science\u00a0350(2-3), 164\u2013173 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"53_CR7","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1137\/050645427","volume":"38","author":"M. Boja\u0144czyk","year":"2008","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM Journal on Computing\u00a038(2), 658\u2013701 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"35","key":"53_CR8","doi-asserted-by":"publisher","first-page":"6821","DOI":"10.1088\/0305-4470\/34\/35\/308","volume":"34","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., Tromp, J., Vit\u00e1nyi, P.: Time and space bounds for reversible simulation. Journal of Physics A: Mathematical and General\u00a034(35), 6821\u20136830 (2001)","journal-title":"Journal of Physics A: Mathematical and General"},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 193\u2013242 (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"issue":"1","key":"53_CR10","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0304-3975(95)80031-4","volume":"143","author":"P. Crescenzi","year":"1995","unstructured":"Crescenzi, P., Papadimitriou, C.H.: Reversible simulation of space-bounded computations. Theoretical Computer Science\u00a0143(1), 159\u2013165 (1995)","journal-title":"Theoretical Computer Science"},{"key":"53_CR11","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.J.: Tree-walking pebble automata. Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, 72\u201383 (1999)","DOI":"10.1007\/978-3-642-60207-8_7"},{"issue":"2-3","key":"53_CR12","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2005.07.014","volume":"345","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoretical Computer Science\u00a0345(2-3), 331\u2013344 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"53_CR13","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.ic.2007.01.008","volume":"205","author":"V. Geffert","year":"2007","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation\u00a0205(8), 1173\u20131187 (2007)","journal-title":"Information and Computation"},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321495.321508","volume":"16","author":"J.E. Hopcroft","year":"1967","unstructured":"Hopcroft, J.E., Ullman, J.D.: Some results on tape bounded Turing machines. Journal of the ACM\u00a016, 168\u2013177 (1967)","journal-title":"Journal of the ACM"},{"key":"53_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/11505877_5","volume-title":"Developments in Language Theory","author":"J. Kari","year":"2005","unstructured":"Kari, J.: Reversible cellular automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol.\u00a03572, pp. 57\u201368. Springer, Heidelberg (2005)"},{"key":"53_CR16","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS 1997, pp. 66\u201375 (1997)"},{"issue":"6","key":"53_CR17","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. Journal of Computer and System Sciences\u00a078(6), 1814\u20131827 (2012)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"53_CR18","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 Journal of Research and Development\u00a05(3), 183\u2013191 (1961)","journal-title":"IBM Journal of Research and Development"},{"issue":"2","key":"53_CR19","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1006\/jcss.1999.1672","volume":"60","author":"K.-J. Lange","year":"2000","unstructured":"Lange, K.-J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. Journal of Computer and System Sciences\u00a060(2), 354\u2013367 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"53_CR20","first-page":"2597","volume":"257","author":"Y. Lecerf","year":"1963","unstructured":"Lecerf, Y.: Machines de Turing r\u00e9versibles. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences\u00a0257, 2597\u20132600 (1963)","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sciences"},{"key":"53_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-642-36315-3_3","volume-title":"Reversible Computation","author":"K. Morita","year":"2013","unstructured":"Morita, K.: A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads. In: Gl\u00fcck, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol.\u00a07581, pp. 29\u201343. Springer, Heidelberg (2013)"},{"issue":"1","key":"53_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.ipl.2005.09.017","volume":"99","author":"A. Muscholl","year":"2006","unstructured":"Muscholl, A., Samuelides, M., Segoufin, L.: Complementing deterministic tree-walking automata. Information Processing Letters\u00a099(1), 33\u201339 (2006)","journal-title":"Information Processing Letters"},{"key":"53_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/3-540-18088-5_19","volume-title":"Automata, Languages and Programming","author":"J.-\u00c9. Pin","year":"1987","unstructured":"Pin, J.-\u00c9.: On the languages accepted by finite reversible automata. In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol.\u00a0267, pp. 237\u2013249. Springer, Heidelberg (1987)"},{"issue":"3","key":"53_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Halting space-bounded computations. Theoretical Computer Science\u00a010(3), 335\u2013338 (1980)","journal-title":"Theoretical Computer Science"},{"key":"53_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-54233-7_154","volume-title":"Automata, Languages and Programming","author":"W. Thomas","year":"1991","unstructured":"Thomas, W.: On logics, tilings, and automata. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 441\u2013454. Springer, Heidelberg (1991)"},{"issue":"1-3","key":"53_CR26","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0167-2789(90)90185-R","volume":"45","author":"T. Toffoli","year":"1990","unstructured":"Toffoli, T., Margolus, N.H.: Invertible cellular automata: A review. Physica D: Nonlinear Phenomena\u00a045(1-3), 229\u2013253 (1990)","journal-title":"Physica D: Nonlinear Phenomena"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T02:11:34Z","timestamp":1558318294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}