{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T10:58:45Z","timestamp":1780743525027,"version":"3.54.1"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319599359","type":"print"},{"value":"9783319599366","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-59936-6_3","type":"book-chapter","created":{"date-parts":[[2017,5,24]],"date-time":"2017-05-24T15:12:32Z","timestamp":1495638752000},"page":"35-51","source":"Crossref","is-referenced-by-count":9,"title":["Reversible Nondeterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,5,25]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weakness and generalizations. In: Motwani, R. (ed.) Foundations of Computer Science (FOCS 1998), pp. 332\u2013341. IEEE Computer Society (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/322326.322334","volume":"29","author":"D Angluin","year":"1982","unstructured":"Angluin, D.: Inference of reversible languages. J. ACM 29, 741\u2013765 (1982)","journal-title":"J. ACM"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-319-40946-7_2","volume-title":"Implementation and Application of Automata","author":"HB Axelsen","year":"2016","unstructured":"Axelsen, H.B., Holzer, M., Kutrib, M.: The degree of irreversibility in deterministic finite automata. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 15\u201326. Springer, Cham (2016). doi: 10.1007\/978-3-319-40946-7_2"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-21254-3_8","volume-title":"Language and Automata Theory and Applications","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. LNCS, vol. 6638, pp. 117\u2013128. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-21254-3_8"},{"key":"3_CR5","doi-asserted-by":"crossref","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, 525\u2013532 (1973)","journal-title":"IBM J. Res. Dev."},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.ipl.2007.12.004","volume":"107","author":"P Garc\u00eda","year":"2008","unstructured":"Garc\u00eda, P., de Parga, M.V., L\u00f3pez, D.: On the efficient construction of quasi-reversible automata for reversible languages. Inform. Process. Lett. 107, 13\u201317 (2008)","journal-title":"Inform. Process. Lett."},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0022-0000(74)80034-6","volume":"9","author":"A Gill","year":"1974","unstructured":"Gill, A., Kou, L.T.: Multiple-entry finite automata. J. Comput. System Sci. 9, 1\u201319 (1974)","journal-title":"J. Comput. System Sci."},{"key":"3_CR8","volume-title":"Introduction to Formal Language Theory","author":"MA Harrison","year":"1978","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Boston (1978)"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-319-21500-6_22","volume-title":"Developments in Language Theory","author":"M Holzer","year":"2015","unstructured":"Holzer, M., Jakobi, S., Kutrib, M.: Minimal reversible deterministic finite automata. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 276\u2013287. Springer, Cham (2015). doi: 10.1007\/978-3-319-21500-6_22"},{"key":"3_CR10","first-page":"453","volume":"6","author":"M Holzer","year":"2001","unstructured":"Holzer, M., Salomaa, K., Yu, S.: On the state complexity of $$k$$ -entry deterministic finite automata. J. Autom. Lang. Comb. 6, 453\u2013466 (2001)","journal-title":"J. Autom. Lang. Comb."},{"key":"3_CR11","first-page":"265","volume":"5","author":"M Kappes","year":"2000","unstructured":"Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states. J. Autom. Lang. Comb. 5, 265\u2013278 (2000)","journal-title":"J. Autom. Lang. Comb."},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0304-3975(96)00224-1","volume":"174","author":"S Kobayashi","year":"1997","unstructured":"Kobayashi, S., Yokomori, T.: Learning approximately regular languages with reversible languages. Theoret. Comput. Sci. 174, 251\u2013257 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-319-41114-9_13","volume-title":"Descriptional Complexity of Formal Systems","author":"GJ Lavado","year":"2016","unstructured":"Lavado, G.J., Pighizzini, G., Prigioniero, L.: Minimal and reduced reversible automata. In: C\u00e2mpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 168\u2013179. Springer, Cham (2016). doi: 10.1007\/978-3-319-41114-9_13"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/3-540-45465-9_16","volume-title":"Automata, Languages and Programming","author":"S Lombardy","year":"2002","unstructured":"Lombardy, S.: On the construction of reversible automata for reversible languages. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 170\u2013182. Springer, Heidelberg (2002). doi: 10.1007\/3-540-45465-9_16"},{"key":"3_CR15","first-page":"223","volume":"E72","author":"K Morita","year":"1989","unstructured":"Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. Trans. IEICE E72, 223\u2013228 (1989)","journal-title":"Trans. IEICE"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BFb0023844","volume-title":"LATIN 1992","author":"J-E Pin","year":"1992","unstructured":"Pin, J.-E.: On reversible automata. In: Simon, I. (ed.) LATIN 1992. LNCS, vol. 583, pp. 401\u2013416. Springer, Heidelberg (1992). doi: 10.1007\/BFb0023844"},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/0022-0000(79)90038-2","volume":"18","author":"PAS Veloso","year":"1979","unstructured":"Veloso, P.A.S., Gill, A.: Some remarks on multiple-entry finite automata. J. Comput. System Sci. 18, 304\u2013306 (1979)","journal-title":"J. Comput. System Sci."}],"container-title":["Lecture Notes in Computer Science","Reversible Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59936-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:50:43Z","timestamp":1750276243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59936-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319599359","9783319599366"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59936-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}