Hiroshi Taniguchi

TCS Journal 1985 Journal Article

Alternating simple multihead finite automata

• Hiroshi Matsuno
• Katsushi Inoue
• Hiroshi Taniguchi
• Itsuo Takanami

This paper introduces the alternating simple multihead finite automaton (ASPMHFA), which can be considered as an alternating version of a simple multihead finite automaton (SPMHFA). We first show that ASPMHFA's are equivalent to ordinary alternating multihead finite automata. We investigate a relationship among the accepting powers of SPMHFA's, ASPMHFA's, and ASPMHFA's with only universal states. We next introduce a simple, natural complexity measure for ASPMHFA's, called ‘leaf-size’, and provide a spectrum of complexity classes of ASPMHFA's, based on simultaneously leaf-size, the number of heads, and the move directions of heads. We finally investigate closure properties (under Boolean operations) of ASPMHFA's.

TCS Journal 1983 Journal Article

A relationship between two-dimensional finite automata and three-way tape-bounded two-dimensional Turing machines

• Katsushi Inoue
• Itsuo Takanami
• Hiroshi Taniguchi

This note supplements a result of Inoue and Takanami (1980) who showed that for any function L(m) such that (i) L(m)⩾log m, and (ii) lim m→∞ [ L(m) m 2 ]= 0 (resp lim m→∞ [ L(m) m log m ] = 0), the class of sets of square tapes accepted by deterministic three-way L(m) tape-bounded two-dimensional Turing machines is incomparable with the class of sets of square tapes accepted by nondeterministic (resp. deterministic) two-dimensional finite automata.

TCS Journal 1983 Journal Article

Two-dimensional alternating turing machines

• Katsushi Inoue
• Itsuo Takanami
• Hiroshi Taniguchi

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).

STOC Conference 1982 Conference Paper

Two-Dimensional Alternating Turing Machines

• Katsushi Inoue
• Itsuo Takanami
• Hiroshi Taniguchi