{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T22:30:59Z","timestamp":1649025059592},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1991,12]]},"abstract":"<jats:p> We introduce an alternating Turing machine with modified accepting structure (denoted by MATM), which is an alternating Turing machine whose accepting condition differs from that of an ordinary alternating Turing machine (denoted by ATM). An MATM has a set of accepting state sets rather than a set of accepting states. An input word x is accepted by an MATM M if there is a computation tree of M on x such that the set of states associated with the leaves of the tree is equal to an accepting state set. Let UTM (MUTM) denote an ATM (MATM) with no existential state. We first investigate a relationship between ATM\u2019s and MATM\u2019s, and show that (i) for any function L(n), L(n) space bounded on-line (off-line) ATM\u2019s are equivalent to L(n) space bounded on-line (off-line) MATM\u2019s, and (ii) for any L(n) such that L(n)\u2265 log log n and lim<jats:sub>n\u2192\u221e<\/jats:sub>L(n)\/n=0, L(n) space bounded on-line MUTM\u2019s are more powerful than L(n) space bounded on-line UTM\u2019s. We then investigate a relationship between online and off-line, and show for example that for any L(n) such that L(n)\u2265 log n and lim<jats:sub>n\u2192\u221e<\/jats:sub>L(n)\/n=0, L(n) space bounded off-line MUTM\u2019s are more powerful than L(n) space bounded on-line MUTM\u2019s. We next show that there exists an infinite hierarchy among accepting powers of L(n) space bounded on-line (off-line) MATM\u2019s and MUTM\u2019s with L(n)\u2265 log log n and lim<jats:sub>n\u2192\u221e<\/jats:sub>L(n)\/n=0. Finally, we investigate closure properties of space bounded on-line (off-line) MATM\u2019s and MUTM\u2019s. <\/jats:p>","DOI":"10.1142\/s0129054191000194","type":"journal-article","created":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T07:12:21Z","timestamp":1101366741000},"page":"401-417","source":"Crossref","is-referenced-by-count":0,"title":["ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE"],"prefix":"10.1142","volume":"02","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":"AKIRA","family":"ITO","sequence":"additional","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":"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,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054191000194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:56:04Z","timestamp":1565178964000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054191000194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":0,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1991,12]]}},"alternative-id":["10.1142\/S0129054191000194"],"URL":"https:\/\/doi.org\/10.1142\/s0129054191000194","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}