ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
Katsushi Inoue, AKIRA ITO, Itsuo Takanami · International Journal of Foundations of Computer Science · 1991
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’s and MATM’s, and show that (i) for any function L(n), L(n) space bounded on-line (off-line) ATM’s are equivalent to L(n) space bounded on-line (off-line) MATM’s, and (ii) for any L(n) such that L(n)≥ log log n and limn→∞L(n)/n=0, L(n) space bounded on-line MUTM’s are more powerful than L(n) space bounded on-line UTM’s. We then investigate a relationship between online and off-line, and show for example that for any L(n) such that L(n)≥ log n and limn→∞L(n)/n=0, L(n) space bounded off-line MUTM’s are more powerful than L(n) space bounded on-line MUTM’s. We next show that there exists an infinite hierarchy among accepting powers of L(n) space bounded on-line (off-line) MATM’s and MUTM’s with L(n)≥ log log n and limn→∞L(n)/n=0. Finally, we investigate closure properties of space bounded on-line (off-line) MATM’s and MUTM’s.