{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:12:22Z","timestamp":1781892742107,"version":"3.54.5"},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p> Given an n-tape automaton M with a one-way read-only head per tape and a right end marker $ on each tape, we say that M is aligned or 0-synchronized (or simply, synchronized) if for every n-tuple x = (x<jats:sub>1<\/jats:sub>,\u2026, x<jats:sub>n<\/jats:sub>) that is accepted, there is a computation on x such that at any time during the computation, all heads, except those that have reached the end marker, are on the same position. When a head reaches the marker, it can no longer move. As usual, an n-tuple x = (x<jats:sub>1<\/jats:sub>,\u2026, x<jats:sub>n<\/jats:sub>) is accepted if M eventually reaches the configuration where all n heads are on $ in an accepting state. In two recent papers, we looked at the problem of deciding, given an n-tape automaton of a given type, whether there exists an equivalent synchronized n-tape automaton of the same type. In this paper, we exhibit various classes of multitape automata which can(not) be converted to equivalent synchronized multitape automata. <\/jats:p>","DOI":"10.1142\/s0129054113400194","type":"journal-article","created":{"date-parts":[[2013,12,27]],"date-time":"2013-12-27T03:17:54Z","timestamp":1388114274000},"page":"799-813","source":"Crossref","is-referenced-by-count":2,"title":["HOW TO SYNCHRONIZE THE HEADS OF A MULTITAPE AUTOMATON"],"prefix":"10.1142","volume":"24","author":[{"given":"OSCAR H.","family":"IBARRA","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"NICHOLAS Q.","family":"TRAN","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Santa Clara University, Santa Clara, CA 95053, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2013,12,27]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"p_3","first-page":"333","volume":"113","author":"Ginsburg G.","year":"1964","journal-title":"Trans. of the Amer. Math. Society"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1966-0201310-3"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"p_12","first-page":"290","volume":"2010","author":"Yu F.","year":"2010","journal-title":"CIAA"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113400194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:10:41Z","timestamp":1565107841000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":6,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2013,12,27]]},"published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1142\/S0129054113400194"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400194","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}