We show that n log n space is sufficient for three-way nondeterministic Turing machines (3NTs) to simulate two-dimensional alternating finite automata (AFs), where n is the number of columns of rectangular input tapes. It is already known that n log n space is necessary for 3NTs to simulate AFs. Thus, our algorithm is optimal in the sense of space complexity point of view. [References: 7]
展开▼
