{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T07:05:13Z","timestamp":1772694313397,"version":"3.50.1"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:p>We reject the proposed proofs of \u201cLemma\u00a09\u201d and \u201cTheorem\u00a013\u201d of an article by Frei et\u00a0al. by pointing out fatal errors in them. In addition, we proved a result that contradicts the latter. We show that it is possible to trade input heads with advice heads and vice versa as long as all heads are allowed to move in both directions and the advice length is not too long and short. We proved that the advice gap between determinism and non-determinism is exponential when there are multiple advice heads, all of which can move in both directions and an input head that cannot move left.<\/jats:p>","DOI":"10.1142\/s0129054125500121","type":"journal-article","created":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T02:57:36Z","timestamp":1745377056000},"page":"349-360","source":"Crossref","is-referenced-by-count":0,"title":["Multi-Head Two-Way Finite Automata with Advice"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7504-1048","authenticated-orcid":false,"given":"Ahmet Bilal","family":"U\u00e7an","sequence":"first","affiliation":[{"name":"Computer Engineering, Bo\u011fazi\u00e7i University, Bebek, 34342, \u0130stanbul, T\u00fcrkiye"}]}],"member":"219","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"S0129054125500121BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80026-7"},{"key":"S0129054125500121BIB002","doi-asserted-by":"crossref","unstructured":"C. Damm and M. Holzer, Automata that take advice, Mathematical Foundations of Computer Science, Vol. 969 (Springer Berlin Heidelberg, 1995), pp. 149\u2013158.","DOI":"10.1007\/3-540-60246-1_121"},{"key":"S0129054125500121BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98355-4_1"},{"key":"S0129054125500121BIB004","unstructured":"P. \u010euris, R. Kr\u00e1lovic, R. Kr\u00e1lovic, D. Pardubsk\u00e1, M. Pa\u0161en and P. Rossmanith, Randomization in non-uniform finite automata,\n                      45th International Symposium on Mathematical Foundations of Computer Science\n                      , eds. J. Esparza and D. Kr\u00e1l,\n                      Leibniz International Proceedings in Informatics\n                      , Vol. 170 (Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2020), pp. 30:1\u201330:13."},{"key":"S0129054125500121BIB005","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054122440063"},{"key":"S0129054125500121BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.038"},{"key":"S0129054125500121BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00237-7"},{"key":"S0129054125500121BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/321495.321508"},{"key":"S0129054125500121BIB009","first-page":"191","volume":"28","author":"Karp R.","year":"1982","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"S0129054125500121BIB010","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.96.18"},{"key":"S0129054125500121BIB011","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411440019X"},{"issue":"3","key":"S0129054125500121BIB012","volume":"19","author":"K\u00fc\u00e7\u00fck U.","year":"2017","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"S0129054125500121BIB013","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"S0129054125500121BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.031"},{"key":"S0129054125500121BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-40608-0_15"},{"key":"S0129054125500121BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2022.104878"},{"key":"S0129054125500121BIB017","author":"Yamakami T.","year":"2008","journal-title":"The Computing Research Repository (CoRR)"},{"key":"S0129054125500121BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007659"},{"key":"S0129054125500121BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.013"},{"key":"S0129054125500121BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28332-1_45"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125500121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T06:11:48Z","timestamp":1772691108000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125500121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":20,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["10.1142\/S0129054125500121"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125500121","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,22]]}}}