3次元マルチインクドットオートマトンの基本的な性質

概要

論文の詳細を見る
Recently, related to the open problems of whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, inkdot Turing machines were introduced. On the other hand, due to the advances in many application areas such as computer vision, robotics, and so forth, it has become increasingly apparent that the study of three-dimensional pattern processing has been of crucial importance. Thus, the research of three-dimensional automata as the computational model of three-dimensional pattern processing has also been meaningful. In Ref., we proposed a three-dimensional multi-inkdot finite automaton and mainly investigated its recognizability of connected pictures. This paper investigates the basic properties of three-dimensional multi-inkdot automata. A three-dimensional alternating Turing machine is a three-dimensional Turing machine (3-TM) whose state set is partitioned into unibersal and existential states. A five-way three-dimensional alternating Turing machine (FV3-ATM) is a three-dimensional alternating Turing machine whose input head can move east, west, south, north, or down, but not up. Let L (m, n) : N^2→N be a function. We say that an FV3-ATM M is L (m, n) space-bounded if, when M accepts the input x, there exists an accepting computation tree at each node of which no more than L (m, n) cells of the worktape are used, where m and n are the numbers of rows and columns of each plane of x, respectively. We denote an L (m, n) space-bounded FV3-ATM by FV3-ATM (L(m, n)). A three-dimensional finite automaton (3-FA) is a 3-TM with no workspace. We denote a deterministic 3-FA [nondeterministic 3-FA, alternating 3-FA with only universal states, alternating 3-FA] by 3-DFA [3-NFA, 3-UFA, 3-AFA]. Further, a three-dimensional k-inkdot finite automaton (3-I_k), k≥1, is a 3-FA with k dots of ink. Thus a 3-I_k is a 3-FA capable of dropping an inkdot on at most k tape-cells of the input for a landmark, once on each cell, but incapable of picking it up or erasing it. In order to distinguish among determinism, nondeterminism, alternation with only universal states, and alternation, we denote a deterministic 3-I_k [nondeterministic 3-I_k, alternating 3-I_k with only universal states, alternating 3-I_k] by 3-DI_k [3-NI_k, 3-UI_k, 3-AI_k]. Define L [FV3-ATM (L(m))]={T|T is accepted by some FV3-ATM (L(m))}. L [3-DFA], etc. are defined similarly. For any family of three-dimensional automata A's, L [A^c] denotes the class of sets of cubic tapes accepted by A's. For a set T of three-dimensional tapes, the complementation of T is denoted by T^^^. Define co-L={T^^^|T∈L}.
社団法人電子情報通信学会の論文
1997-03-06

3次元マルチインクドットオートマトンの基本的な性質

スポンサーリンク

概要

著者

関連論文

スポンサーリンク