{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T23:14:39Z","timestamp":1783379679910,"version":"3.54.6"},"reference-count":16,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"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":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.ic.2026.105462","type":"journal-article","created":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T23:26:26Z","timestamp":1778196386000},"page":"105462","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Improved bounds on the length of shortest strings accepted by two-way finite automata"],"prefix":"10.1016","volume":"311","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1249-5173","authenticated-orcid":false,"given":"Olga","family":"Martynova","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/j.ic.2026.105462_bib0001","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1002\/j.1538-7305.1962.tb00480.x","article-title":"On non-computable functions","volume":"41","author":"Rad\u00f3","year":"1962","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"10.1016\/j.ic.2026.105462_bib0002","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/3427361.3427369","article-title":"The busy beaver frontier","volume":"51","author":"Aaronson","year":"2020","journal-title":"SIGACT News"},{"issue":"4","key":"10.1016\/j.ic.2026.105462_bib0003","first-page":"407","article-title":"Regular expressions: new results and open problems","volume":"10","author":"Ellul","year":"2005","journal-title":"J. Autom. Lang. Comb."},{"issue":"1","key":"10.1016\/j.ic.2026.105462_bib0004","first-page":"19:1","article-title":"Shortest paths in one-counter systems","volume":"15","author":"Chistikov","year":"2019","journal-title":"Log. Methods Comput. Sci."},{"key":"10.1016\/j.ic.2026.105462_bib0005","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2023.105127","article-title":"Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs","volume":"296","author":"Martynova","year":"2024","journal-title":"Inf. Comput."},{"issue":"2","key":"10.1016\/j.ic.2026.105462_bib0006","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1137\/0210020","article-title":"The rational index: a complexity measure for languages","volume":"10","author":"Boasson","year":"1981","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.ic.2026.105462_bib0007","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(92)90269-L","article-title":"Rational indexes of generators of the cone of context-free languages","volume":"95","author":"Pierre","year":"1992","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.ic.2026.105462_bib0008","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s00224-023-10159-3","article-title":"Rational index of languages defined by grammars with bounded dimension of parse trees","volume":"68","author":"Shemetova","year":"2024","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.ic.2026.105462_bib0009","doi-asserted-by":"crossref","unstructured":"L. Alpoge, T. Ang, L. Schaeffer, J. Shallit, Decidability and shortest strings in formal languages, in: Descriptional Complexity of Formal Systems (DCFS 2011, Limburg, Germany, 25\u201327 July 2011), LNCS 6808, 55\u201367.","DOI":"10.1007\/978-3-642-22600-7_5"},{"key":"10.1016\/j.ic.2026.105462_bib0010","doi-asserted-by":"crossref","unstructured":"D. Kozen, Lower bounds for natural proof systems, FOCS 1977, 254\u2013266.","DOI":"10.1109\/SFCS.1977.16"},{"key":"10.1016\/j.ic.2026.105462_bib0011","doi-asserted-by":"crossref","unstructured":"C.A. Kapoutsis, Removing bidirectionality from nondeterministic finite automata, Mathematical Foundations of Computer Science (MFCS 2005, Gdansk, Poland, 29 August\u20132 September 2005), LNCS 3618, 544\u2013555.","DOI":"10.1007\/11549345_47"},{"issue":"4","key":"10.1016\/j.ic.2026.105462_bib0012","first-page":"315","article-title":"On the length of shortest strings accepted by two-way finite automata","volume":"180","author":"Dobronravov","year":"2021","journal-title":"Fundam. Inf."},{"key":"10.1016\/j.ic.2026.105462_bib0013","doi-asserted-by":"crossref","unstructured":"S. Krymski, A. Okhotin, Longer shortest strings in two-way finite automata, in: G. Jir\u00e1skov\u00e1, G. Pighizzini (Eds.), Descriptional Complexity of Formal Systems, LNCS 12442, 2020, pp. 104\u2013116.","DOI":"10.1007\/978-3-030-62536-8_9"},{"key":"10.1016\/j.ic.2026.105462_bib0014","series-title":"NCMA 2013","article-title":"One-way simulation of two-way finite automata over small alphabets","author":"Geffert","year":"2013"},{"key":"10.1016\/j.ic.2026.105462_bib0015","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2020.104631","article-title":"Reversibility of computations in graph-walking automata","volume":"275","author":"Kunc","year":"2020","journal-title":"Inf. Comput."},{"key":"10.1016\/j.ic.2026.105462_bib0016","doi-asserted-by":"crossref","unstructured":"M. Radionova, A. Okhotin, Sweeping permutation automata, in: Non-Classical Models of Automata and Applications (NCMA 2023, Famagusta, North Cyprus 18\u201319 September 2023), EPTCS 388, pp. 110\u2013124.","DOI":"10.4204\/EPTCS.388.11"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000593?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000593?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T22:28:00Z","timestamp":1783376880000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540126000593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":16,"alternative-id":["S0890540126000593"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105462","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Improved bounds on the length of shortest strings accepted by two-way finite automata","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105462","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"105462"}}