{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T05:00:55Z","timestamp":1648789255824},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[1992,8]]},"abstract":"<jats:p> This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimensional alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular acceptors (NUPCAs), and show that \u03a9 ( diameter \u00d7 log diameter ) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimensional alternating Turing machines (2-ATMs) operating in small space, and show that if L (n) is a two-dimensionally space-constructible function such that lim <jats:sub>n \u2192 \u221e<\/jats:sub> L (n)\/ loglog n &gt; 1 and L (n) \u2264 log n, and L\u2032 (n) is a function satisfying L\u2032 (n) =o (L(n)), then there exists a set accepted by some strongly L (n) space-bounded two-dimensional deterministic Turing machine, but not accepted by any weakly L\u2032 (n) space-bounded 2-ATM, and thus there exists a rich space hierarchy for weakly S (n) space-bounded 2-ATMs with loglog n \u2264 S (n) \u2264 log n. <\/jats:p>","DOI":"10.1142\/s0218001492000126","type":"journal-article","created":{"date-parts":[[2004,11,24]],"date-time":"2004-11-24T19:50:24Z","timestamp":1101325824000},"page":"211-225","source":"Crossref","is-referenced-by-count":1,"title":["TWO TOPICS CONCERNING TWO-DIMENSIONAL AUTOMATA OPERATING IN PARALLEL"],"prefix":"10.1142","volume":"06","author":[{"given":"KATSUSHI","family":"INOUE","sequence":"first","affiliation":[{"name":"Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University, Ube 755, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ITSUO","family":"SAKURAMOTO","sequence":"additional","affiliation":[{"name":"Department of Mechanical and Electrical Engineering, Tokuyama National College of Technology, Tokuyama 745, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MAKOTO","family":"SAKAMOTO","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Oshima National College of Maritime Technology, Oshima-Gun 742-21, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ITSUO","family":"TAKANAMI","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Systems Engineering, 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\/S0218001492000126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:15:19Z","timestamp":1565129719000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001492000126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,8]]},"references-count":0,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1992,8]]}},"alternative-id":["10.1142\/S0218001492000126"],"URL":"https:\/\/doi.org\/10.1142\/s0218001492000126","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,8]]}}}