Two-dimensional alternating turing machines

This paper introduces a two-dimensional alternating Turing machine (2-ATM) which can be considered as a natural extension of a one-dimensional alternating Turing machine to two dimensions. This paper also introduces a three-way two-dimensional alternating Turing machine (TR2-ATM) which is an alternating version of a three-way two-dimensional Turing machine. We first investigate a relationship between the accepting powers of space bounded 2-ATM's (or TR2-ATM's) and ordinary space bounded two-dimensional Turing machines (or three-way two-dimensional Turing machines). We then introduce a simple, natural new complexity measure for 2-ATM's (or TR2-ATM's), called ‘leaf-size’, and provide a spectrum of complexity classes based on leaf-size bounded computations. We finally investigate recognizability of connected patterns by 2-ATM's (or TR2-ATM's).

Authors

• Katsushi Inoue
• Itsuo Takanami
• Hiroshi Taniguchi

Keywords

No keywords are indexed for this paper.