{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T06:10:24Z","timestamp":1697868624436},"reference-count":16,"publisher":"Wiley","issue":"9","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1986,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Previously, we proposed a (<jats:italic>k, l<\/jats:italic>)\u2010neighborhood template \u03b4\u2010type bounded cellular acceptor (abbreviated as \u03b4\u2010\u2010BCA (<jats:italic>k, l<\/jats:italic>)), which is composed of a pair of converters and a configuration\u2010reader and operates on a two\u2010dimensional tape. Its basic properties have already been discussed. \u03b4\u2010BCA (<jats:italic>k, l<\/jats:italic>) is a parallel automaton, which, in a sense, is a generalization of the one\u2010dimensional bounded cellular acceptor. This paper attempts a more detailed examination of the properties of \u03b4\u2010BCA (<jats:italic>k, l<\/jats:italic>), and compares its accepting power with those of other automata operating on the two\u2010dimensional tape. The objects of comparison are the various kinds of two\u2010dimensional finite automata and various kinds of parallel sequential array acceptors. It is known that there exists an equivalent tape\u2010bounded Turing machine for each of these automata in the sense of the accepting power. Consequently, the comparison of the accepting power of \u03b4\u2010BCA (<jats:italic>k, l<\/jats:italic>) and those of two\u2010dimensional automata amounts in a sense to the evaluation of the accepting power of \u03b4\u2010BCA (<jats:italic>k, l<\/jats:italic>) in terms of the tape complexity of the tape\u2010bounded Turing machine.<\/jats:p>","DOI":"10.1002\/scj.4690170903","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:32:20Z","timestamp":1183811540000},"page":"20-28","source":"Crossref","is-referenced-by-count":0,"title":["Relationship between the accepting powers of (k, <i>l<\/i>)\u2010neighborhood template \u03b4\u2010type one\u2010dimensional bounded cellular acceptors and other types of two\u2010dimensional automata"],"prefix":"10.1002","volume":"17","author":[{"given":"Hiroshi","family":"Taniguchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsushi","family":"Inoue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Itsuo","family":"Takanami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeko","family":"Seki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(79)90021-5"},{"key":"e_1_2_1_3_2","first-page":"9","article-title":"Relation between two\u2010dimensional on\u2010line tessellation acceptors and one\u2010dimensional bounded cellular acceptors","volume":"59","author":"Inoue K.","year":"1976","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_4_2","first-page":"3","article-title":"The (k, l)\u2010neighborhood template \u03b4\u2010type bounded cellular acceptors","volume":"64","author":"Taniguchi H.","year":"1981","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_5_2","first-page":"6","article-title":"(k, l)\u2010neighborhood template \u03b4\u2010type bounded cellular acceptors\u2014hierarchies based on the difference of neighborhood templates","volume":"65","author":"Taniguchi H.","year":"1982","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_6_2","first-page":"9","article-title":"(k, l)\u2010neighborhood template \u03b4\u2010type bounded cellular acceptors\u2014 Refinements of hierarchical properties","volume":"66","author":"Taniguchi H.","year":"1983","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"M.BlumandC.Hewitt. Automata on a 2\u2010dimensional tape I.E.E.E. Symp. on SWAT p.155(1967).","DOI":"10.1109\/FOCS.1967.6"},{"key":"e_1_2_1_8_2","first-page":"2","article-title":"Three\u2010way two\u2010dimensional simple multihead finite automata\u2014Hierarchical properties","volume":"62","author":"Inoue K.","year":"1979","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(79)90017-3"},{"key":"e_1_2_1_10_2","first-page":"3","article-title":"Some notes on parallel sequential array acceptors","volume":"58","author":"Inoue K.","year":"1975","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90011-2"},{"key":"e_1_2_1_12_2","first-page":"12","article-title":"Language recognition ability of several two\u2010dimensional tape automata and their relation to tape complexities","volume":"60","author":"Morita K.","year":"1977","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_13_2","first-page":"2","article-title":"Accepting powers of two\u2010dimensional automata over square tapes","volume":"63","author":"Inoue K.","year":"1980","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_14_2","series-title":"Computer Science Technical Report Series","volume-title":"Sequential and parallel picture acceptors, TR\u2010613, AFOSR\u201077\u20133271","author":"Rosenfeld A.","year":"1977"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(82)90045-7"},{"key":"e_1_2_1_16_2","first-page":"9","article-title":"Some properties of parallel sequential array acceptors and two\u2010dimensional two\u2010marker atuomata","volume":"59","author":"Inoue K.","year":"1976","journal-title":"Trans. (D) I.E.C.E., Japan"},{"key":"e_1_2_1_17_2","first-page":"10","article-title":"Some properties of two\u2010dimensional on\u2010line tessellation acceptors","volume":"59","author":"Inoue K.","year":"1976","journal-title":"Trans. (D) I.E.C.E., Japan"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170903","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T17:15:52Z","timestamp":1697822152000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":16,"journal-issue":{"issue":"9","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170903"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170903","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}