3次元有限オートマトンと3次元層を持った時間限定ボトムアップピラミッドセルラアクセプタの受理能力の関係

概要

論文の詳細を見る
In this paper, we introduce a new model of acceptor on a three-dimensional pattern, called the time-bounded bottom-up pyramid cellular acceptor with three-dimensional layers whose input tapes are restricted to cubic ones (3-UPC AC), and investigate a relationship between the accepting powers of 3-UPCAc's and three-dimesional finite automata whose input tapes are restricted to cubic ones (3-FAc's). We first show that nondeterministic 3-UPCAc's are more powerful than nondeterministic 3-FAc's. We next show that O ((diameter) 2 × log diameter) time is sufficient for deterministic 3-U PC Ac's to simulate deterministic 3-FAc's, and that O ((diameter) 3) time is sufficient for deterministic 3-UPCAc's to simulate nondeterministic 3-FAc's. Finally, we show that Ω ((diameter) 2 × log diameter) time is necessary for nondeterministic 3-UPCAc's to simulate alternating 3-FAc's.