使用交替图灵机的并行算法的结构复杂性研究-猫眼课题宝

使用交替图灵机的并行算法的结构复杂性研究

批准号：

06780249

负责人：

山本博章

金额：

$0.58万

依托单位：

Shinshu University

依托单位国家：

日本

项目类别：

Grant-in-Aid for Encouragement of Young Scientists (A)

财政年份：

1994

资助国家：

日本

项目状态：

已结题

起止时间：

1994 至 --

来源：

https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780249/

关键词：

交代チューリング機械リバーサル計算量領域計算量構造的計算量交代数

中文摘要

翻译

点击翻译按钮获取中文摘要

英文摘要

本研究では当初の目標に沿って、次の2点に関して考察を進め、新しい結果を得た。1.ヘッド反転数が一定の場合における交代数の違いによる能力差について2.ヘッド反転数が制限された交代チューリング機械の領域計算量について以下、それぞれの今年度の成果について述べる。1.ヘッド反転数が一定の場合における交代数の違いによる能力差についてまず、ここではヘッド反転数が制限された交代チューリング機械を考える。交代チューリング機械は、AND状態、OR状態に相当する状態を持ち、このAND状態OR状態が計算中に交代する回数が交代数である。交代チューリング機械において、状態が交代するときに使用しているテープ量がヘッド反転数を制限している関数によって制限されるモデルを考えたとき、我々は、このようなモデルでは交代数の違いによって能力差が生じないことを示した。もしこのような制限がなければ、従来、交代数によって能力差が生じることが知られていた。2.ヘッド反転数が制限された交代チューリング機械の領域計算量について従来、ヘッド反転数が制限された決定性チューリング機械および非決定性チューリング機械に対しては、その領域計算量が知られていた。しかし、交代チューリング機械に対しては、その領域計算量が明らかにされていなかった。本研究では、拡張通過列を導入することにより、ヘッド反転数が制限された1テープ交代チューリング機械はその領域計算量も自動的にある関数によって制限されてしまうことを示した。また、この結果から、従来より知られていたいくつかの結果が簡単に導かれることも示した。

期刊论文(2)

专著(0)

科研奖励(0)

会议论文

山本博章: "リバーサル限定チューリング機械における交代数の能力について" 電子情報通信学会技術報告. COMP94-27. 27-36 (1994)

Hiroaki Yamamoto：“关于反转限制图灵机的交替次数的能力”IEICE COMP94-27 (1994)。

DOI： --

发表时间：

期刊：

影响因子： --

作者：

[]