{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T13:19:01Z","timestamp":1774271941031,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T00:00:00Z","timestamp":1769817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T00:00:00Z","timestamp":1769817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["23-11-00133"],"award-info":[{"award-number":["23-11-00133"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s00236-025-00519-6","type":"journal-article","created":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T06:33:20Z","timestamp":1769841200000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sweeping permutation automata"],"prefix":"10.1007","volume":"63","author":[{"given":"Maria","family":"Radionova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,31]]},"reference":[{"issue":"3","key":"519_CR1","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1145\/322326.322334","volume":"29","author":"D Angluin","year":"1982","unstructured":"Angluin, D.: Inference of Reversible Languages. Journal of the ACM 29(3), 741\u2013765 (1982). https:\/\/doi.org\/10.1145\/322326.322334","journal-title":"Journal of the ACM"},{"key":"519_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104672","volume":"283","author":"E Bakinova","year":"2022","unstructured":"Bakinova, E., Basharin, A., Batmanov, I., Lyubort, K., Okhotin, A., Sazhneva, E.: Formal languages over GF(2). Information and Computation 283, 104672 (2022)","journal-title":"Information and Computation"},{"key":"519_CR3","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-030-93489-7_3","volume":"13037","author":"V Geffert","year":"2021","unstructured":"Geffert, V., Okhotin, A.: Deterministic one-way simulation of two-way deterministic finite automata over small alphabets, Descriptional Complexity of Formal Systems. LNCS 13037, 26\u201337 (2021). https:\/\/doi.org\/10.1007\/978-3-030-93489-7_3","journal-title":"LNCS"},{"key":"519_CR4","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-030-48516-0_10","volume":"12086","author":"M Hospod\u00e1r","year":"2020","unstructured":"Hospod\u00e1r, M., Mlyn\u00e1r\u010dik, P.: Operations on permutation automata, DLT. LNCS 12086, 122\u2013136 (2020). https:\/\/doi.org\/10.1007\/978-3-030-48516-0_10","journal-title":"LNCS"},{"issue":"1","key":"519_CR5","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.ic.2016.12.007","volume":"253","author":"G Jir\u00e1skov\u00e1","year":"2017","unstructured":"Jir\u00e1skov\u00e1, G., Okhotin, A.: On the state complexity of operations on two-way finite automata. Inf. Comput. 253(1), 36\u201363 (2017)","journal-title":"Inf. Comput."},{"key":"519_CR6","doi-asserted-by":"publisher","unstructured":"Kapoutsis, C.A.: Removing bidirectionality from nondeterministic finite automata, Mathematical Foundations of Computer Science (MFCS,: Gdansk, Poland, 29 August-2 September 2005). LNCS 3618, 544\u2013555 (2005). https:\/\/doi.org\/10.1007\/11549345_47","DOI":"10.1007\/11549345_47"},{"key":"519_CR7","unstructured":"Kapoutsis, C. A.: Algorithms and Lower Bounds in Finite Automata Size Complexity, Ph.\u00a0D. thesis, Massachusetts Institute of Technology, (2006)"},{"key":"519_CR8","doi-asserted-by":"publisher","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata, 38th Annual Symposium on Foundations of Computer Science (FOCS 1997, Miami Beach, Florida, USA, 19\u201322 October 1997), IEEE, 66\u201375. https:\/\/doi.org\/10.1109\/SFCS.1997.646094","DOI":"10.1109\/SFCS.1997.646094"},{"key":"519_CR9","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.tcs.2012.04.010","volume":"449","author":"M Kunc","year":"2012","unstructured":"Kunc, M., Okhotin, A.: State complexity of operations on two-way finite automata over a unary alphabet. Theoretical Computer Science 449, 106\u2013118 (2012)","journal-title":"Theoretical Computer Science"},{"key":"519_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104631","volume":"275","author":"M Kunc","year":"2020","unstructured":"Kunc, M., Okhotin, A.: Reversibility of computations in graph-walking automata. Information and Computation 275, 104631 (2020). https:\/\/doi.org\/10.1016\/j.ic.2020.104631","journal-title":"Information and Computation"},{"key":"519_CR11","doi-asserted-by":"publisher","unstructured":"Margolis, S. W., Pin, J.-\u00c9.: Products of group languages, FCT p.285\u2013299 (1985). https:\/\/doi.org\/10.1007\/BFb0028813","DOI":"10.1007\/BFb0028813"},{"key":"519_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114489","volume":"995","author":"A Okhotin","year":"2024","unstructured":"Okhotin, A., Radionova, M., Sazhneva, E.: GF(2)-operations on basic families of formal languages. Theoretical Computer Science 995, 114489 (2024)","journal-title":"Theoretical Computer Science"},{"key":"519_CR13","doi-asserted-by":"publisher","unstructured":"Pin, J.-\u00c9.: On the languages accepted by finite reversible automata, Automata, Languages and Programming, 14th International Colloquium, (ICALP: Karlsruhe, Germany, July 13\u201317, 1987). LNCS 267, 237\u2013249 (1987). https:\/\/doi.org\/10.1007\/3-540-18088-5_19","DOI":"10.1007\/3-540-18088-5_19"},{"key":"519_CR14","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BFb0023844","volume":"583","author":"J\u00c9 Pin","year":"1992","unstructured":"Pin, J.\u00c9.: On reversible automata, LATIN \u201992, 1st Latin American Symposium on Theoretical Informatics (S\u00e3o Paulo, Brazil, April 6\u201310. LNCS 583, 401\u2013416 (1992). https:\/\/doi.org\/10.1007\/BFb0023844","journal-title":"LNCS"},{"key":"519_CR15","doi-asserted-by":"publisher","unstructured":"Radionova, M., Okhotin, A.: Sweeping permutation automata, Non-Classical Models of Automata and Applications (NCMA,: Famagusta, North Cyprus, 18\u201319 September 2023). EPTCS 388, 110\u2013124 (2023). https:\/\/doi.org\/10.4204\/EPTCS.388.11","DOI":"10.4204\/EPTCS.388.11"},{"key":"519_CR16","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2023010","volume":"57","author":"C Rauch","year":"2023","unstructured":"Rauch, C., Holzer, M.: On the accepting state complexity of operations on permutation automata. RAIRO\u2014 Theoretical Informatics and Applications 57, 9 (2023). https:\/\/doi.org\/10.1051\/ita\/2023010","journal-title":"RAIRO\u2014 Theoretical Informatics and Applications"},{"key":"519_CR17","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3, 198\u2013200 (1959). https:\/\/doi.org\/10.1147\/rd.32.0198","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"519_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M Sipser","year":"1980","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci. 21(2), 195\u2013202 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90034-3","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"519_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01691347","volume":"2","author":"G Thierrin","year":"1968","unstructured":"Thierrin, G.: Permutation automata. Mathematical Systems Theory 2(1), 83\u201390 (1968). https:\/\/doi.org\/10.1007\/BF01691347","journal-title":"Mathematical Systems Theory"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00519-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00519-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00519-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T12:25:35Z","timestamp":1774268735000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00519-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,31]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["519"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00519-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,31]]},"assertion":[{"value":"7 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"3"}}