{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T00:50:44Z","timestamp":1648860644612},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[1989,12]]},"abstract":"<jats:p> We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM<jats:sub>1<\/jats:sub> (2-NM<jats:sub>1<\/jats:sub>), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM<jats:sub>1<\/jats:sub>s (2-NM<jats:sub>1<\/jats:sub>s) is n log n (n<jats:sup>2<\/jats:sup>), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM<jats:sub>1<\/jats:sub>s (2-NM<jats:sub>1<\/jats:sub>s) is 2<jats:sup>O(n log n)<\/jats:sup> (2 <jats:sup>O(n<jats:sup>2<\/jats:sup>)<\/jats:sup>), where n is the number of columns of rectangular input tapes. <\/jats:p>","DOI":"10.1142\/s0218001489000309","type":"journal-article","created":{"date-parts":[[2004,11,28]],"date-time":"2004-11-28T21:14:37Z","timestamp":1101676477000},"page":"393-404","source":"Crossref","is-referenced-by-count":1,"title":["THE SIMULATION OF TWO-DIMENSIONAL ONE-MARKER AUTOMATA BY THREE-WAY TURING MACHINES"],"prefix":"10.1142","volume":"03","author":[{"given":"AKIRA","family":"ITO","sequence":"first","affiliation":[{"name":"Technical College, Yamaguchi University,  Ube, 755, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KATSUSHI","family":"INOUE","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Yamaguchi University,  Ube, 755, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ITSUO","family":"TAKANAMI","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Yamaguchi University,  Ube, 755, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001489000309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:14:17Z","timestamp":1565129657000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001489000309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":0,"journal-issue":{"issue":"03n04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1989,12]]}},"alternative-id":["10.1142\/S0218001489000309"],"URL":"https:\/\/doi.org\/10.1142\/s0218001489000309","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}