Some Properties of Multihead Automata on Four-Dimensional Input Tapes
スポンサーリンク
概要
- 論文の詳細を見る
The comparative study of the computational powers of deterministic and nondeterministic computations is one of the central tasks of complexity theory. This paper investigates the computational power of nondeterministic computing devices with restricted nondeterminism. There are only few results measuring the computational power of restricted nondeterminism. In general, there are three possibilities to measure the amount of nondeterminism in computation. In this paper, we consider the possibility to count the number of different nondeterministic computation paths on any input. In particular, we deal with seven-way four-dimensional finite automata with multiple input heads operating on four-dimensional input tapes.
- 2009-09-30
論文 | ランダム
- 原腸形成を制御するペプチド (ウニの発生学--新展開を迎えたウニの生物学)
- スラム街の子どもたちin Cebu
- 臓器移植法からみる人の死の変遷
- 機能性食品素材が肥満モデルマウスの体脂肪蓄積に及ぼす影響
- 介護福祉士における災害介護教育の必要性の検討--災害時における人間の尊厳と生活を守る為に介護の視点から考える